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

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!

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.