Row Of A Matrix With Maximum Ones
You are given a 2D matrix (containing either ‘0’ or ‘1’) of size N x M, where each row is in sorted order. Find the 0-based index of the first row that has the maximum number of 1's.

For example :

For given 2D matrix: [ [ 0, 1, 1 ], [ 1, 1, 1 ], [ 0, 0, 1 ] ] The maximum number of 1’s are present in row 1 i.e. 3, considering the 0-based indexing so the result is 1.

Note :

If two rows have the same number of 1’s then return the row with a lower index.

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows. The first line of each test case contains two integers ‘N’ and ‘M’ representing the number of rows and number of columns of the 2D matrix. Each of the next N lines contains M space-separated integers representing the elements of the matrix ARR.

Output Format :

For each test case,print the row index which contains the maximum number of 1’s.

Note :

You do not need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 ≤ T ≤ 50 1 ≤ N,M ≤ 100 0 ≤ ARR[i][j] ≤ 1 Where ARR[i][j] denotes the matrix elements. Time Limit: 1 sec

Question

Row Of A Matrix With Maximum Ones

You are given a 2D matrix (containing either ‘0’ or ‘1’) of size N x M, where each row is in sorted order. Find the 0-based index of the first row that has the maximum number of 1's.

For example :

For given 2D matrix:

[     [ 0,  1,  1 ],
      [ 1,  1,  1 ],
      [ 0,  0,  1 ]   ]

The maximum number of 1’s are present in row 1 i.e. 3, considering the 0-based indexing so the result is 1.

Note :

If two rows have the same number of 1’s then return the row with a lower index.

Input Format :

 The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.

 The first line of each test case contains two integers ‘N’ and ‘M’ representing the number of rows and number of columns of the 2D matrix.

 Each of the next N lines contains M space-separated integers representing the elements of the matrix ARR.

Output Format :

For each test case,print the row index which contains the maximum number of 1’s.

Note :

You do not need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 ≤ T ≤ 50
1 ≤ N,M ≤ 100
0 ≤ ARR[i][j] ≤ 1

Where ARR[i][j] denotes the matrix elements.

Time Limit: 1 sec

Accepted Answer

Brute Force

Our intuition is to traverse the given matrix row by row, and keep on counting the number of ‘1’s in each row and compare the count with max. And finally, return the index of the row with the maximum ‘1’s. This is a brute force kind of approach.

Just remember one thing while considering two rows have the same number of 1’s then we need to return the row with a lower index.

Space Complexity: O(1)Explanation:

O(1)

Since no extra space is required, so the overall space complexity will be O(1).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We traverse through the matrix row-wise which will take ‘N’ iterations and for each row of size ‘M’ will take O(M) complexity to traverse the row, so the overall time complexity will be O(N*M).

Python (3.5)

"""

    Time Complexity: O(N * M)

    Space Complexity: O(1)



    Where N is the number of rows and M is the number of columns in the given matrix.

"""





def maximumOnesRow(matrix):

    n = len(matrix)



    #    maxCount stores the maximum number of 1s found till now and ans is the index of that particular row.

    maxCount = 0



    for i in range(n):

        #    Count for number of ones for the current row.

        curr = 0

        for j in range(len(matrix[i])):

            #   Increment count if the value is 1.

            if matrix[i][j] == 1:

                curr += 1



        #    Update curr row and maximum count if the current row has the maximum number of ones.

        if curr > maxCount:

            ans = i

            maxCount = curr



    #    Return the row with maximum number of ones.

    return ans

    pass

Java (SE 1.8)

/*

    Time Complexity: O(N*M)

    Space Complexity: O(1)



    where 'N' is the number of rows and 'M' is the number of columns in the given matrix.

*/



import java.util.ArrayList;



public class Solution 

{

    public static int maximumOnesRow(ArrayList> matrix) 

    {

        int n = matrix.size();



        //    maxCount stores the maximum number of 1s found till now and ans is the index of that particular row.

        int maxCount = 0, ans=-1;



        for (int i = 0; i < n; i++) 

        {

            //    Count for number of ones for the current row.

            int curr = 0;



            for (int j = 0; j < matrix.get(i).size(); j++) 

            {

                //    Increment count if the value is 1.

                if (matrix.get(i).get(j) == 1) 

                {

                    curr++;

                }

            }



            //    Update curr row and maximum count if the current row has the maximum number of ones.

            if (curr > maxCount) 

            {

                ans = i;

                maxCount = curr;

            }

        }



        //    Return the row with maximum number of ones.

        return ans;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*M)

    Space Complexity: O(1)



    where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

*/



int maximumOnesRow(vector> &matrix)

{

    int n=matrix.size();



    //    maxCount stores the maximum number of 1s found till now and ans is the index of that particular row.

    int maxCount = 0, ans;



    for(int i=0;i    {

        //    Count for number of ones for the current row.

        int curr=0;

        

        for(int j=0;j        {

            //    Increment count if the value is 1.

            if(matrix[i][j]==1)

            {

                curr++;

            }

        }



        //    Update curr row and maximum count if the current row has the maximum number of ones.

        if(curr>maxCount)

        {

            ans = i;

            maxCount = curr;

        }

    }

    

    //    Return the row with maximum number of ones.

    return ans;

}

Accepted Answer

Binary Search

In the previous approach, we were iterating through all the elements of the matrix. Do we really need to do that? Think of how we can search for a point where the 1’s starts to appear since all the rows are sorted as given in the question.

Steps to follow towards a better approach :

Since each row is sorted, we can use Binary Search to count the ‘1’s in each row.
We find the index of the first instance of ‘1’ in each row which the first time we find a ‘1’ in each row.
The count of ‘1’s will be equal to the total number of columns minus the index of the first ‘1’.
And finally, we can return the row index with the maximum count of ‘1’s.

Space Complexity: O(1)Explanation:

O(1)

Since no extra space is required, so the overall space complexity will be O(1).

Time Complexity: O(nlogn)Explanation:

O(N*log(M)), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We traverse through the matrix row-wise which will take ‘N’ iterations and for each row of size ‘M’ will take O(log(M)) complexity in binary search, so the overall time complexity will be O(N*log(M)).

Python (3.5)

"""

    Time Complexity: O(N * log(M))

    Space Complexity: O(1)



    Where N is the number of rows and M is the number of columns in the given matrix.

"""





def maximumOnesRowHelper(row, low, high):

    if high >= low:

        #    Get the middle index.

        mid = low + (high - low) // 2



        #    Check if the element at middle index is first 1.

        if (mid == 0 or row[mid - 1] == 0) and row[mid] == 1:

            return mid



        #    If the element is 0, recur for the right side.

        elif row[mid] == 0:

            return maximumOnesRowHelper(row, (mid + 1), high)



        #    If element is not first 1, recur for the left side.

        else:

            return maximumOnesRowHelper(row, low, (mid - 1))



    return -1





def maximumOnesRow(matrix):



    #    Initialize max values

    ans, max = 0, -1



    n = len(matrix)



    # Traverse for each row and count number of 1s by finding the index of first 1

    for i in range(n):

        m = len(matrix[i])



        index = maximumOnesRowHelper(matrix[i], 0, m - 1)



        if index != -1 and m - index > max:

            max = m - index

            ans = i



    #    Return the row with maximum number of ones.

    return ans



    pass

Java (SE 1.8)

/*

    Time Complexity: O(N*log(M))

    Space Complexity: O(1)



    where 'N' is the number of rows and 'M' is the number of columns in the given matrix.

*/



import java.util.ArrayList;



public class Solution 

{

	private static int maximumOnesRowHelper(ArrayList row, int low, int high) 

	{

		if (high >= low) 

		{

			//    Get the middle index.

			int mid = low + (high - low) / 2;



			//    Check if the element at middle index is first 1.

			if ((mid == 0 || row.get(mid - 1) == 0) && row.get(mid) == 1) 

			{

				return mid;

			}



			//    If the element is 0, recur for the right side.

			else if (row.get(mid) == 0) 

			{

				return maximumOnesRowHelper(row, (mid + 1), high);

			}



			//    If element is not first 1, recur for the left side.

			else 

			{

				return maximumOnesRowHelper(row, low, (mid - 1));

			}

		}



		return -1;

	}



	public static int maximumOnesRow(ArrayList> matrix) 

	{

		//    Initialize max values

		int ans = 0, max = -1;



		int n = matrix.size();



		// Traverse for each row and count number of 1s by finding the index of first 1

		int i, index;



		for (i = 0; i < n; i++) 

		{

			int m = matrix.get(i).size();



			index = maximumOnesRowHelper(matrix.get(i), 0, m - 1);



			if (index != -1 && m - index > max) 

			{

				max = m - index;

				ans = i;

			}

		}



		//    Return the row with maximum number of ones.

		return ans;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log(M))

    Space Complexity: O(1)



    where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

*/



int maximumOnesRowHelper(vector &row, int low, int high)

{

    if (high >= low)

    {

        //    Get the middle index.

        int mid = low + (high - low) / 2;



        //    Check if the element at middle index is first 1.

        if ((mid == 0 || row[mid - 1] == 0) && row[mid] == 1)

        {

            return mid;

        }



        //    If the element is 0, recur for the right side.

        else if (row[mid] == 0)

        {

            return maximumOnesRowHelper(row, (mid + 1), high);

        }



        //    If element is not first 1, recur for the left side.

        else

        {

            return maximumOnesRowHelper(row, low, (mid - 1));

        }

    }



    return -1;

}



int maximumOnesRow(vector> &matrix)

{

    //    Initialize max values

    int ans = 0, max = -1;



    int n = matrix.size();



    // Traverse for each row and count number of 1s by finding the index of first 1

    int i, index;



    for (i = 0; i < n; i++)

    {

        int m = matrix[i].size();



        index = maximumOnesRowHelper(matrix[i], 0, m - 1);



        if (index != -1 && m - index > max)

        {

            max = m - index;

            ans = i;

        }

    }



    //    Return the row with maximum number of ones.

    return ans;

}

Accepted Answer

Optimized Method

In the previous approach, we were searching in each of the given matrix. Can you think of a case in which we can really skip a row in order to make our approach more optimized?

Steps are as follows :

Get the index of the leftmost ‘1’ in the first row.
Do the following for every row after the first row.
If the element on the left of the previous leftmost ‘1’ is ‘0’, then we will ignore this row.
Else, move left until a ‘0’ is found.
Update the leftmost index to this index and “maxIndex” (row index with the maximum number of ones) to be the current row.
Finally, we can return the “maxIndex”.

Space Complexity: O(1)Explanation:

O(1)

Since no extra space is required, so the overall space complexity will be O(1).

Time Complexity: O(1)Explanation:

O(N+M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

Since we can possibly go as far left as we came ahead in the first step, so the overall time complexity will be O(N+M).

Python (3.5)

"""

    Time Complexity: O(N+M)

    Space Complexity: O(1)



    Where N is the number of rows and M is the number of columns in the given matrix.

"""





def maximumOnesRowHelper(row, low, high):

    if high >= low:

        #    Get the middle index.

        mid = low + (high - low) // 2



        #    Check if the element at middle index is first 1.

        if (mid == 0 or row[mid - 1] == 0) and row[mid] == 1:

            return mid



        #    If the element is 0, recur for the right side.

        elif row[mid] == 0:

            return maximumOnesRowHelper(row, (mid + 1), high)



        #    If element is not first 1, recur for the left side.

        else:

            return maximumOnesRowHelper(row, low, (mid - 1))



    return -1





def maximumOnesRow(matrix):

    #    Initialize first row as row with max 1s

    ans = 0



    n = len(matrix)



    m = len(matrix[0])



    #    The function maximumOnesRowHelper() returns index of first 1 in row 0. Use this index to initialize the index of leftmost 1 seen so far.

    j = maximumOnesRowHelper(matrix[0], 0, m - 1)



    if j == -1:

        #    if 1 is not present in first row

        j = m - 1



    for i in range(1, n):



        #    Move left until a 0 is found

        while j > 0 and matrix[i][j - 1] == 1:

            j -= 1

            ans = i



    #    Return the row with maximum number of ones.

    return ans

    pass

Java (SE 1.8)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1)



    where 'N' is the number of rows and 'M' is the number of columns in the given matrix.

*/



import java.util.ArrayList;



public class Solution 

{

	private static int maximumOnesRowHelper(ArrayList  row, int low, int high) 

	{

		if (high >= low) 

		{

			//    Get the middle index.

			int mid = low + (high - low) / 2;



			//    Check if the element at middle index is first 1.

			if ( (mid == 0 || (mid >0 && row.get(mid - 1) == 0)) && row.get(mid) == 1) 

			{

				return mid;

			}

			//    If the element is 0, recur for the right side.

			else if (row.get(mid) == 0) 

			{

				return maximumOnesRowHelper(row, (mid + 1), high);

			}

			//    If element is not first 1, recur for the left side.

			else 

			{

				return maximumOnesRowHelper(row, low, (mid - 1));

			}

		}



		return -1;

	}



	public static int maximumOnesRow(ArrayList>  matrix) 

	{

		//    Initialize first row as row with max 1s

		int ans = 0;



		int n = matrix.size();



		int m = matrix.get(0).size();



		//    The function maximumOnesRowHelper() returns index of first 1 in row 0. Use this index to initialize the index of leftmost 1 seen so far.

		int j = maximumOnesRowHelper(matrix.get(0), 0, m - 1);



		if (j == -1) 

		{

			//    if 1 is not present in first row

			j = m - 1;

		}



		for (int i = 1; i < n; i++) 

		{



			//    Move left until a 0 is found

			while (j > 0 && matrix.get(i).get(j - 1) == 1) 

			{

				j = j - 1;

				ans = i;

			}



		}

		//    Return the row with maximum number of ones.

		return ans;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N+M)

    Space Complexity: O(1)



    Where 'N' is the number of rows and 'M' is the number of columns in the given matrix.

*/



int maximumOnesRowHelper(vector &row, int low, int high)

{

    if (high >= low)

    {

        //    Get the middle index.

        int mid = low + (high - low) / 2;



        //    Check if the element at middle index is first 1.

        if ((mid == 0 || row[mid - 1] == 0) && row[mid] == 1)

        {

            return mid;

        }



        //    If the element is 0, recur for the right side.

        else if (row[mid] == 0)

        {

            return maximumOnesRowHelper(row, (mid + 1), high);

        }



        //    If element is not first 1, recur for the left side.

        else

        {

            return maximumOnesRowHelper(row, low, (mid - 1));

        }

    }



    return -1;

}



int maximumOnesRow(vector> &matrix)

{

    //    Initialize first row as row with max 1s

    int ans = 0;



    int n= matrix.size();



    int m = matrix[0].size();



    //    The function maximumOnesRowHelper() returns index of first 1 in row 0. Use this index to initialize the index of leftmost 1 seen so far.

    int j = maximumOnesRowHelper(matrix[0], 0, m - 1);

    

    if (j == -1)

    { 

        //    if 1 is not present in first row

        j = m - 1;

    }



    for (int i = 1; i < n; i++)

    {

        

        //    Move left until a 0 is found

        while (j > 0 && matrix[i][j-1] == 1)

        {

            j = j - 1;

            ans = i;

        }

        

    }

    //    Return the row with maximum number of ones.

    return ans;

}

You are given a 2D matrix (containing either ‘0’ or ‘1’) of size N x M, where each row is in sorted order. Find the 0-based index of the first row that has the maximum number of 1's.

For example :

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Cisco Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Cisco Software Engineer