Which row has the most 1s in a 0-1 matrix with all 1s "on the left"?

Question

Problem

Each row of an n x n matrix consists of 1's and 0's such that in any row, all 1's come before any 0's. Find row containing most no of 1's in O(n).

Example

1 1 1 1 1 0  <- Contains maximum number of 1s, return index 1 1 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 

I found this question in my algorithms book. The best I could do took O(n logn) time. How to do this in O(n)?

Answer 1

Start at 1,1.

If the cell contains 1, you're on the longest row so far; write it down and go right. If the cell contains 0, go down. If the cell is out of bounds, you're done.