Given a boolean matrix sorted row wise. Return a row with max number of 1

Question

I came across a problem of Matrices but was trying to figure out the optimal solution. Problem statement is the question topic itself. Further see below

Example
Input matrix

  0 1 1 1
  0 0 1 1
  1 1 1 1  // this row has maximum 1s
  0 0 0 0

Output: 2

My Solution : Now since rows are sorted, i thought of performing binary search in each row with the first occurrence of 1, and then count of 1 will be total number of columns minus index of 1st 1.

This will do it in O(m*logn), but I was curious to know the logic if this could be done in linear time.

Thank you!

Answer 1

Start a cursor in the top right. In each row, step left until you reach the last 1 in the row. Then step down. If you step down and the cursor points to a 0, step down again. Never go right. You're looking for the row that has a 1 furthest to the left, so you never need to look to the right. The runtime is O(n+m), since you go through every row, stepping down m times, and you make a total of n steps left at most. Here's some pseudocode, assuming that the matrix is a list of lists:

bestrow = 0
leftmost = matrix.width

for i = matrix.height to 0:
    row = matrix[i]
    while row[leftmost - 1] == 1:
        leftmost--
        bestrow = i

return bestrow

If you translate the code literally, you may have problems with a matrix of all 0's, or if some row has all 1's. These are pretty easy to deal with, and the point of the pseudocode is just to communicate the general algorithm.

Answer 2

The solution for this problem depends on the number of elements in each row and the number of columns. Here is an approach.

Step 1: Simple do a binary && operation on all elements in each column until you get a true which means we found a column which has at least one one. This take max n steps where n is number of columns.

Step 2: Now do a search for one from top to bottom in that column which gives you the row with max number of ones. This takes max of m steps.where m is number of rows So overall it takes O(m+n) steps

It also helps you find multiple rows if any with the same property