Leftmost Column with at Least a One- Best Trade-off problem to discuss different time complexities

  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:

Leetcode Link

May 21, 2021

Subscribe by Email

Follow Updates Articles from This Blog via Email