Find index of the row containing maximum number of 1’s in a binary matrix

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 –
 

Download   Run Code

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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
arandomguy
Guest
arandomguy

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

arandomguy
Guest
arandomguy

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