Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of A, all the 1's come before any 0's in that row. Assuming $A$ is already in memory, describe a method running in O($n$) time for finding the row of $A$ that contains the most 1's.
I don't understand how this is possible if the array was not already sorted. How can you possibly do this in O($n$) time? What if every element in the array was a 1? Then any algorithm I could think of would run in O($n^2$).