Given a binary M × N row-wise sorted matrix, find a row that contains the maximum number of 1's in linear time.

For example,

Input:
 
[ 0  0  0  1  1 ]
[ 0  0  1  1  1 ]
[ 0  0  0  0  0 ]
[ 0  1  1  1  1 ]
[ 0  0  0  0  1 ]
 
Output: The maximum 1’s are present in row 4

Practice this problem

The idea is to start from the top-right corner of the matrix and do the following:

  • If the current cell has value 1, continue moving left till we encounter 0, or all columns are processed;
  • If the current cell has value 0, continue moving down till we encounter 1, or all rows are processed.

Finally, return the row index of the last cell in which we have seen 1. The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

The maximum 1’s are present in the row 4

Java


Download  Run Code

Output:

The maximum 1’s are present in the row 4

Python


Download  Run Code

Output:

The maximum 1’s are present in the row 4

The time complexity of the proposed solution is O(M + N) for an M × N matrix and doesn’t require any extra space.