Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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. –  Listing Jan 16 '12 at 23:27

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Oh wow that is so simple. But I don't see where you got 2n from. Also, what would happen if every element is a 0? –  styfle Jan 16 '12 at 22:59
    
very nice and tricky –  Saeed Jan 16 '12 at 23:22
    
@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
    
To me it seems like you could do it in n steps instead of 2n steps. Since the outer loop would go from 1 to n (for each column) and inside: if A[row][col]=1, mark as answer, else, row = row + 1. The next iteration of the loop would then check the next column in the row with most ones (current answer). Does that make sense? –  styfle Jan 17 '12 at 0:09
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.