Suppose that each row of an nxn 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 (not O(n^2) time) for finding the row of A that contains the most 1's.

Since there can be multiple rows containing the most 1's, let's assume it's enough to find any one such row. Make sure that your algorithm works even if A consists of all 0's or all 1's.

Instructor's Comment: i) explain your idea in words (and possibly using illustrations) first, ii) give pseudocode, and iii) discuss (prove) correctness and running time