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.