Leftmost Column with at Least a One:
This problem is a best example for trade-off with the interviewer and it gives the right signal to the interviewer to judge whether your concepts are clear or not in-terms of time complexity.
Let me explain you in a easy way to understand the problem with different approaches and which one is better .
Problem Statement:
Given a row-sorted binary matrix binaryMatrix
, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1
.
Ex:
Input:
[0, 0, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 1]
[0, 0, 0, 0 ,0, 1]
[0, 0, 0, 0, 1, 1]
Output:
2
Approach 1 (M * N) :
Traverse through the entire matrix and find out the first occurrence of 1 in each row and store whichever is minimum and return that as the result.This approach is easy but it takes m*n time complexity where m is no of rows and n is no of columns.
Approach 2 (M logN):
Apply the Binary Search on each row to identify where the 1 is ending in each row and store the minimum value from all the rows . In this approach , since you are traversing all the rows and for each row it takes logN to get the 1's position .So, the time complexity would be M*logN.
Approach 3 (M + N) :
Start from right most corner (row = 0 and col = N- 1 where N is the max column no ) and keep moving to left until 1 is seen by incrementing the column. Increase the row number whenever first 0 is seen .You do not have to go back to check previous column of the current row has 1 or not as we need to return the minimum column number from the Grid . In this approach, at max the column no can be traversed upto 0 where the row number started from 0 (From right most top column to left most bottom row ) which is M + N traversal .
Solution:
private int findLeftMostColumn(int[][] grid) {
int m = 0;
int n = grid[0].length;
while (m < grid.length && n >= 0) {
if(grid[m][n] == 1){
n--;
} else{
m++;
}
}
return n + 1;
}
The question is which approach is the best approach ?
Definitely either 2 or 3 approach is better than 1 . Lets see which one is better (Either 2 or 3).
Lets assume ,we have 1000 rows and 1024 columns (I took this numbers just for better understanding ) .
M = 1000
N = 1024
logN = 10 (as 1024 can be written as 2^10 => log2^N = log2^10 => N = 10)
So,
M*logN = 1000 * 10 => 10,000
M + N = 1000 + 1024 => 2024
In this case , M + N < M * logN .
Let's increase the column no now and see which one is better .
M = 1000
N = 1,073,741,824
logN = 30 ( as 1,073,741,824 can be written as 2^30 => log2^N = log2^30 => N = 30
So,
M * logN = 1000 * 30 => 30000
M + N = 1000 + 1,073,741,824 =>1,073,742,824
in this case it is clearly shown M * logN is far better than M + N .
It is proven that M * logN is better when N is big .
Reference Link:
Subscribe by Email
Follow Updates Articles from This Blog via Email
No Comments