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

Search Element in a rotated sorted array --- Made it easy .

 This article is about how easily an element can be searched in a rotated sorted array with Binary search .

Input

nums = [4,5,6,7,0,1,2], target = 0

Output:

4

Solution :

There are three steps to solve this problem easily. 

Step 1 : Find out the min element.

Step 2: Apply the standard Binary search on left side of minimum element. 

Step 3: Apply the standard Binary search on right side of minimum element .

First let us find out the minimum element in the array which is 0 ( indexed at 4) and apply the classical Binary search to left side array and right side array .  if any one of the function returns the right value then it can returned as the answer . 

                                      

  

Time Complexity :                                    

For the above 3 steps approach , We will apply Binary Search for the step 1 which is O(logn) time complexity where "n" is no of elements in the array. For step 2 and step 3 we will apply standard Binary search algorithm .So , the total time complexity is O(logn) + O(logn) + O(logn) which is equal to O(logn) as we can ignore the constant time from O(3logn).

Space Complexity :

space complexity is going to be a O(1) as we are not using any extra space . 

Code:

Among all 3 steps , first step is difficult and if you understand this step the many problems can be easily solved of this kind. The idea is, array can be split into two arrays as we do in Binary search and the check if the middle element is less than its previous element and next element of course we check the out of boundary case . if it is minimum then we can return as it is the result . If not, check which side of the array is sorted , out min element will always be on the other side which is not sorted . so, we can keep checking element until we find the min element by following the above step. 

class Solution {
    public int search(int[] nums, int target) {

        int min =  getMinIndex(nums);
        int left = BinarySearch(nums,  0,  min - 1,  target);
        int right = BinarySearch(nums,  min,  nums.length - 1,  target);

        return left == -1 && right == -1 ? - 1 : left == -1 ? right : left;
    }

    private int getMinIndex(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        int n = nums.length;

        while(left <= right){
            if(nums[left] <= nums[right]){
                return left;
            }
            int mid = left + (right - left) / 2;
            int next = ( mid + 1 ) % n;
            int prev = (mid - 1 + n) % n;

            if(nums[mid] <= nums[prev] && nums[mid] <= nums[next]){
                return mid;
            } else if(nums[left] <= nums[mid]){
                left = mid + 1;
            } else if(nums[mid] <= nums[right]){
                right = mid - 1;
            }
        }
        return 0;
    }

    private int BinarySearch(int[] nums, int left, int right, int target){
        while(left <= right){
            int mid = (left + right ) / 2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] > target){
                right = mid - 1;
            } else{
                left = mid + 1;
            }

        }
        return -1;
    }

}

Code may look little bit lengthy but trust me if you get this then implementation is very easy . 

so now we know how to find out min element in rotated array . Below all the problems can be solved by using above approach .

https://leetcode.com/problems/search-in-rotated-sorted-array/

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Pattern - 1:Sliding Window

This pattern is used when any problem statement has something like calculate(sum , avg, max, math,duplicate) with in subarray,sublist and substring (widow).

Technique: 

• Keep Increasing the window if the computed value is less than the given  criteria.
• Print the computed value if criteria is exactly met.
• keep Decreasing  the window   if the computed value is more than the given criteria.                                          

General snippet of Code:

int slidingWindowPattern(int[] nums , int k){

    int windowStart  = 0;
    int ComputeValue = 0;

    for(int windowEnd = 0; windowEnd < nums.length; windowEnd++){

        int endValue = nums[windowEnd];
        ComputeValue += endValue;// Keep adding the value

        if(windowEnd > k){
            int startValue = nums[windowStart];
            ComputeValue -= startValue;
        }
    }
    return ComputeValue;
}

Example 1 - Easy:

Given an input array nums , find the sum of all subarray of size k.

Input:
nums = [1, 2, 3, 4, 5, 6, 7] k = 3
Output:
result = [6, 9, 12, 15, 18]

Explanation:

First Window : 1 + 2 + 3 = 6 

Second Window : 2 + 3 + 4 = 9

Third Window : 3 + 4 + 5 = 12

Fourth Window : 4 + 5 + 6 = 15

Fifth Window : 5 + 6 + 7 = 18

Solution :

As discussed above , 

• keep increasing the window until the size of the window is less than K by storing the summation of all elements into a computed sum variable  . 
• If the window size is equal to K then we store into result array .
• If the window is greater than K then we shrink the window by removing the starting window element from the summation variable.

int[] findSumOfSubArrayOfSizeK(int[] nums, int k){

    int[] result = new int[nums.length - (k - 1)];
    int windowStart  = 0;
    int ComputeSum = 0;

    for(int windowEnd = 0; windowEnd < nums.length; windowEnd++){

        int endValue = nums[windowEnd];
        ComputeSum += endValue;// Keep Increasing the window if the computed value is less than the given  criteria

        if(windowEnd >= k - 1){
            int startValue = nums[windowStart];
            result[windowStart++] = ComputeSum; //Add the computed sum if criteria is met.
            ComputeSum -= startValue;//keep Decreasing  the window   if the computed value is more than the given criteria.  
        }
    }
    return result;
}