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.
0
appears after1
in a row. – khachik