Was asked this question in a coding round:
Given a matrix of 0's and 1's where, in any row - the values will be ascending order. i.e 1's are always after the 0's. Consider the example :
0,0,0,1,1
0,0,1,1,1
0,0,0,0,1
1,1,1,1,1
0,0,0,0,0
Find the first column that has a 1. ( from left - right )
In this case the first column ( in row 4 ) has a 1. Answer is 1
I suggested a column wise traversal across all rows and exit when the current column encounters 1 in any of the rows.
Since the worse case performance is n * n ( comparing every element in the matrix) the interviewer wasn't pleased and was looking for a efficient solution - what is an efficient solution here ?
Take advantage of the fact that the rows are sorted which is evident from "in any row - the values will be ascending order. i.e 1's are always after the 0's"
Let there be m
rows and n
columns. Do a binary search on first row to figure out the first 1
and store that index in some variable, say index
(One may think of a better variable name. I am just focused here on solving the problem optimally.) Continue binary search on every row, update the index
if the first column containing 1
has lesser index than the index
. After doing binary search on every row, you'll end up with the result in index
variable.
Time complexity: m
rows * log2(n
columns) i.e. O(m * log2(n))
.
This is the approach I could think of, which is better than the brute force approach having O(mn)
time complexity. I don't think there would be a more optimal approach in terms of time and space complexity, as one has to search for the first 1
in every row.
[I don't think I should add the details on how to do a binary search to figure out the first column containing a 1
. In case someone isn't very familiar with binary search, I leave this trivial part as an exercise.]