How To 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 –
 
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).

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?