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 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
$\endgroup$
4
  • 2
    $\begingroup$ What is the context where you have encountered this problem? Can you credit the original source? $\endgroup$
    – EnEm
    Commented Jun 18 at 4:07
  • 2
    $\begingroup$ It's exercise C-1.24 in Algorithm Design and Applications (Goodrich). $\endgroup$ Commented Jun 18 at 4:09
  • 3
    $\begingroup$ One overwhelming thing to realize is simply that each of these "rows" "all the 1's comes before any 0's in that row" is nothing more than "a number", ie the index where the the zero appears on that row. $\endgroup$
    – Fattie
    Commented Jun 18 at 14:56
  • 3
    $\begingroup$ Dang, I was excited thinking some magic was going on here, until I saw that all the ones had to come before all the zeros in each row. $\endgroup$
    – Sam Estep
    Commented Jun 18 at 18:09

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ Love how concrete this pseudocode is, but I needed a verbal description. The algorithm will "walk down" the matrix like a staircase (perhaps with uneven steps). Start at the top left. For each row, if the current location contains a 1, walk forward until you hit the first 0. Then walk down and repeat from where you left off. At the end of the process, the last row where you saw a 1 is going to be the answer. This description also helps with the runtime analysis: in total you take at most n steps forward and n steps down. To argue correctness, it might help to draw a picture. $\endgroup$ Commented Jun 19 at 16:14
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I like this answer because it has a dynamic programming feel to it. $\endgroup$
    – qwr
    Commented Jun 19 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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