# Linear time algorithm for $n\times n$ array of 1's and 0's

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$).

-
Perhaps better off here: scicomp.stackexchange.com ? – Daniel Freedman Jan 16 '12 at 22:51
@DanielFreedman: I looked at the site and it doesn't seem to have any questions about asymptotics. – styfle Jan 16 '12 at 22:52
If every element in the array was $1$ you can already terminate after looking at the first row because there can't be more than $n$ ones. – Listing Jan 16 '12 at 23:27

Hint: Once you've seen a $1$ in column $k$, you never have to look at columns $\le k$ in any row anymore. You can move on to column $k+1$. In each step, if you see a $0$, you can exclude that row, and if you see a $1$ you can move on to the next column. Thus there can be at most $2n$ steps. I didn't fill in all the details because this is homework; feel free to ask if it's too vague.
@styfle: The $2n$ comes from the fact that there are $n$ rows and $n$ columns and each step excludes either a row or a column, so after at most $n+n=2n$ steps there's nothing left to exclude. If every element is a $0$, you just look at all the $0$s in the first column and then pick any of the rows. (That was part of the detail I'd left out: You start in the first column.) – joriki Jan 16 '12 at 23:52
@styfle: I don't think so. If you increment the column in every step, even if the step increments the row, then you can miss a better row. For instance, what would your algorithm do if the only $1$s are one in the first row and two in the last row? I think it would miss the last row and give the first row as the answer? – joriki Jan 17 '12 at 0:42
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}