Given a binary M x N row-wise sorted matrix, find a row which contains maximum number of 1 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:** Maximum 1’s are present in the row 4

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

– if current cell has value 1, continue moving left till we encounter 0 or all columns are processed, else

– if current cell has value 0, continue moving down till we encounter 1 or all rows are processed.

Finally, we return the row index of last cell in which we have seen 1.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> using namespace std; #define M 5 #define N 5 int findRowIndex(bool mat[][N]) { // i, j stores current row and column index int i, j; // stores row number with maximum index int row = -1; // start from top-rightmost cell of the matrix i = 0, j = N - 1; while (i <= M - 1 && j >= 0) { // move left if current cell has value 1 if (mat[i][j]) j--, row = i; // update row number else // else move down i++; } return row + 1; } int main() { bool mat[M][N] = { { 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 } }; int rowIndex = findRowIndex(mat); // rowIndex = 0 means no 1's are present in the matrix if (rowIndex) cout << "Maximum 1's are present in the row " << rowIndex; return 0; } |

`Output:`

Maximum 1’s are present in the row 4

The time complexity of above solution is `O(M + N)` and auxiliary space used by the program is `O(1)`.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

what is the logic behind this? How does it work correctly?

ok got it. didn’t read the problem carefully “row wise sorted binary matrix”.

I dont think this is right..you only move down if you hit a 0 in the very last element in every row.. therefore you get 2. I tried the exact code and it didn’t work. Second of all, how is the complexity O(N+M) ? You are going through the matrix row-wise and column-wise. I think it’s O(N*M).

Code works fine. I think you’re confused somewhere. Please read the problem statement again and try to relate the logic. If you still think you’re right, kindly provide a test case where the code fails.

Also time complexity remains O(N+M) since we either go left or bottom, and not in other two directions at any point.

Sorry, just made the same mistake as arandomguy below. The solution is correct.