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: