Arrays. Find row with most 1's, in O(n)

Question

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 comes before any 0's in that row. Assume $A$ is already in memory, describe a method running in $O(n)$ for finding the the row of $A$ that contains the most 1's.

What I tried, is to start from the last column, loop down the entries in that row, and return the index of that row if that entry is 1. It's not the most naive method, but i doubt it is $O(n)$, since if the array consist of only one 1 in the first column and last row, it will loop $n^2$ times...

Any better suggestions?

def most(A):
    for i in range(len(A)-1, -1, -1):
        for j in range(len(A)):
            if A[j,i] == 1:
                return j

Answer 1

Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and for the sake of simplicity, has only one row $r_0$ with maximum number of $1$'s.

findMaxRowSum($A$, $n$)

• Inititalize $i \leftarrow 1$, $j\leftarrow 0$ and $r_{mx} \leftarrow 1$
• Do the below iteratively, terminating when told to:
  • If $j = n$, exit loop
  • Otherwise if $A_{i,\:j+1} = 1$, update $j \leftarrow j+1$ and $r_{mx} \leftarrow i$
  • Otherwise if $i=n$, exit loop
  • Otherwise update $i \leftarrow i+1$
• Output $r_{mx}$

Lets say the row at which matrix $A$ has maximum $1$'s is $r_0$, then the above algorithm will (1) reach $i=r_0$ at some point and (2) will iterate $j$ to the max number of $1$'s in the row.

You can also improve this easily to output the whole list of maximum $1$ rows in $A$, using $\mathcal{O}(n)$ memory and $\mathcal{O}(n)$ time.

Answer 2

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked in O(1), then you only need to examine k’ - k array elements, not k’.

Very often a problem has an obvious solution that is slow. In this case, determine the number of 1s in each row and return the largest number. Then you need to realise that the problem didn’t actually ask for the number of 1s in each row. So you think: How can I solve the problem without the obvious step I thought I needed?

BTW. You can determine the number of 1s in each row in O(log n) by finding the first 0 using binary search. So a solution in O(n ln n) would have been easy.