1
$\begingroup$

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

  • 2
    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.2012-01-16

1 Answers 1

7

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.

  • 0
    Oh I see what $y$ou're saying. It has to stay on the k+1 column to check rows that are further down. You're right.2012-01-17