Find the row representing the smallest integer in row wise sorted matrix

Question

I was asked this question on in a recent Java telephonic interview:

You are given an NxN binary (0-1) matrix with following properties:

• Each row is sorted (sequence of 0's followed by sequence of 1's)
• Every row represents an unsigned integer (by reading the bits)
• Each row is unique

Example:

0 1 1
1 1 1
0 0 1

The bit values in each row is sorted and the rows represent the integers 3, 7 and 1.

Find the row representing the smallest integer. In the example above, the answer is row 3, which represents the integer 1.

I started with brute force of quadratic complexity. The interviewer replied saying I was not exploiting the sorted property.

After thinking a lot I used binary search on each row and it came to O(nlogn). He asked if I could improve any further. I thought a lot but failed to improve.

I would appreciate if anyone can give any pointers on imporoving it.

Another example:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

The answer will be row 3, which represents the integer 0.

Answer 1

Start with row 1. Go right until you hit the first 1. Then go down to row 2, but remain in the same column and repeat the process of going right until you hit a 1. Do this repeatedly. The row in which you last stepped right is your answer.

This is an O(N+M) solution (for an NxM matrix, or O(N) for a square NxN matrix as given in the question).

Using your example of:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

The .'s here represent the path traversed:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

This solution works on non-square matrixes, retaining a worst case O(N+M) efficiency for an NxM matrix.

Why does this work? The guarantee that the numbers will be sorted means every row will be a series of 0's followed by a series of 1's. So the magnitude of a row is equivalent to how far right you can go before hitting a 1. So if a row can ever take you further by just following the 0's, then it must be longer than anything we've processed before.

Python code:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j += 1
    ans = i

print "Row", ans+1, "".join(map(str, li[ans]))

There is also a simpler solution, because of the constraints of always having a square NxN matrix and distinct rows together. Together they mean that the row with the lowest value will be either 0 0 ... 0 1 or 0 0 ... 0 0. This is because there are N of N+1 possible numbers represented in the matrix, so the "missing" number is either 0 (in which case the smallest value represented is 1) or it's something else (smallest value is 0).

With this knowledge, we check the column second from the right for a 0. When we find one, we look to its right and if that contains another 0 we have our answer (there can only be one row ending in a 0). Otherwise, we continue to search the column for another 0. If we don't find another 0, the first one we found was the row we're looking for (there can only be one row ending in 01 and since there was none ending in 00, this is the smallest).

Python code:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans+1, "".join(map(str, li[ans]))

That solution answers the question with least difficulty in O(N), but generalising it to handle non-square NxM matrixes or non-distinct numbers will make its worst-case efficiency O(N^2). I personally prefer the first solution.

Answer 2

the lowest number must be 0 or 1. (because there are no duplications and the rows are sorted). all you have to do is go over the last column, if ti contains 0 lowest number is 0 else lowest number is 1.

EDIT - explanation
In N rows with the constraint you sated there can be a maximum of N+1 unique values.
so for sure at least 0 or 1 must be in the matrix....

Edit 2 - algorithm

//assuming the matrix is 0 indexed base
for i = 0...N-1
  if M[i][N-1] == 0
    return "Value is 0 in row i";
for i = 0...N-1
  if M[i][N-2] == 0
    return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.

Answer 3

Since the numbers are unique and since the digits are sorted, it is quite clear that for any value of N, the smallest number can be either of the form [0(N-1 times) followed by 1] or 0(N times).

For example, for N=4, the smallest number can either be 0001 or 0000.

In other words, second last digit of the number we wish to find HAS to be 0. And the last digit can either be 0 or 1

This problem then reduces to just finding these patterns in the array, which can be done using a simple for loop

int rowNum = -1;

for(int i=0;i<N;i++)
{
    if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
    {
        rowNum = i;

        if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
        {
            continue;
        }
        else
         //If number of the form 0000 was found, exit. 
         //No other number can be lesser than 0000
        {
            break;
        }
    }
}
return rowNum;

This algorithm would have complexity O(n)

Answer 4

You want to find a rows with maximum number of zeros.

• Start at arr[0][0]
• If it is 0, check the element towards right of it, arr[0][1].
• If it's not 0 then skip that row and start checking at the element in the next row below the current element.

Keep doing till you go past the last row/last column or you find a row with all zeros.

Algorithm:

i = 0 
j = 0 
answer = 0 

# continue till i is a valid index.
while(i<N) 

        # continue till j is valid index and ele is 0.
        while(j < N AND arr[i][j] == 0)

                # move towards right.
                j++ 

                #update answer.
                answer = i 

                # found a row with all zeros.
                if(j == N)  
                        break all loops.
                end-if

        end-while

        # skip current row..continue on next row.    
        i++ 

end-while

print answer

The complexity of this is O(N+N) which is O(N), that is linear.

Java implementation

Related question Which makes use of exact same trick

How to efficiently search in an ordered matrix?

Answer 5

Since the bits in each row are sorted, once you have found a 1 bit, all bits to the right must be 1 too. In other words, the array only stores values of the form 2^n-1.

So the answer is the row with the most zero entries is the smallest.

However, since only 2**m-1 entries can be present, and there are n of those, and no two are the same we can deduce more - for any N there are N+1 such values. So either 0 or 1 must be present as we know there are no duplicates.

So look for an empty row (which is hte only one with rightmost column zero). If you don't find it, the answer is 1, else it's 0.

O(N)

Answer 6

Start at the top-left.

The first row is the best row so far.

Repeat until you reach the bottom:
  If you're not already over a 1:
    Go right until you find a 1.
    This row is the best row so far.
  Go down one row.

Report the best row that was found.

You never go up or left - you only go down (n-1) times and right no more than (n-1) times, making this O(n). This exploits the sortedness by realizing that you never have to go left to check for a 1 - if there is a 1 somewhere to the left, then there is also a 1 in the current spot (and thus the number in this row is at least as big as the one in the previous row).

Answer 7

How about looping each line in reverse order and checking where the 1s end and the zeroes start?

In fact it is guaranteed that in NxN, the worst case is that 0 won't be there. So you can just check the last 2 entries of each row. Which makes it linear.

Since my explanation was not understood, here it is in somewhat pseudo code:

int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
   byte[] row = array[k];
   if (row[row.length - 1] == 0) {
       lowestRow = k;
       break;
   }
   if (row[row.length - 2] == 0) {
       lowestRow = k;
       //possibly look for all-zeroes, so not breaking
   }
}

Answer 8

You have to start with the last column, and check if the sum of the element is N-1, once you have found the column with the sum = N-1 search the column containing a 0 and this is the one you are looking for...

Answer 9

An optimised version of @codaddict

int best = N;
int answer = -1;

for(int i=0;i<N;i++)
   for(int j=0;j<best;j++) 
       if (arr[i][j] != 0) {
          best = j;
          answer = i;
        }

The inner loops stops as soon as it determines this row won't be the better than the current answer. This could cut out alot of searching down rows which are longer than the best answer so far.

Answer 10

Find which row has the first non zero value in the furthest column. If it is binary, with the MSB on the left, and the LSB on the right the answer is the row that starts with the most zeros.

Answer 11

I would add this as a comment to Jeremy's answer if i could, because his solution is mostly correct. Also, I like the approach. In many instances it will be MUCH faster than other answers. There is a possible problem. If "Each row is sorted." does not mean that all ones are shifted to the right, but has some other implication(I can think of a couple of implications. I would need more from the individual asking the question). One problem...what about 0011 and 0010. Rows are sorted could mean that the algorithm you are implementing is already used. The algorithm specified in his answer cannot distinguish between the two. I would store the index of both answers in an array. If array length is 1 then you have a solution, otherwise you need to recurse further...just a thought. If anyone reads this that can post comments on others posts please reference this in a comment to his post. It is a serious problem, and it would be upsetting to have a technically incorrect answer get the check. If my comment is added I will delete my answer completely.

Answer 12

The smallest number can be 0 which looks like (0000...0000) or 1 which looks like (0000...0001).

Every larger number looks like (xxxx...xx11). So you should check the next to last digit in every row. If it is 0 then check if the last digit is 0. If it is it is the smallest number. If not, then remember the row number and continue looking for row with 0 on the next to last digit. If you find it, this will be the smallest number. If not, the first found number is smallest one.

This is the solution with N+1 steps (worst case scenario) which is O(N) complexity.

Answer 13

I don't know if it's admitted, but if it's sorted don't you need just to convert each row to decimal number and choose the row with the lower one. example:

[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1

The solution is the row with value 0. OR?

Answer 14

I have written a O(n) algorithm, similar to what has been stated above, we start from top-left corner and work downwards:

a = [
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [0, 0, 0, 0],
        [1, 1, 1, 1]
    ]
a2 = [
        [0, 0, 0, 0],
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [1, 1, 1, 1]
    ]

def search(a):
    n = len(a)
    c = 0
    r = 0
    best_row = 0
    while c<n and r<n:
        if a[r][c] == 0:
            c += 1
        else:
            best_row = r
            r += 1

    if c==n : best_row = r
    print( " best row: %d" % best_row )

search( a )
search( a2 )