Leftmost Column with at Least a One. Facebook interview question. Thought process from brute force to binary search.

#javascript #computerscience #career #programming

Question: In a binary matrix (all elements are 0 and 1), every row is sorted in ascending order (0 to the left of 1). Find the leftmost column index with a 1 in it.

Eg :

Input:
[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 1, 1, 1],
 [0, 0, 0, 0]]
Output: 1

Input:
[[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]]
Output: -1

Let's solve this from brute force and later optimize it.

Brute force: O(M*N)

A simple brute force solution would be to iterate over each row and find the first index for which array element is 1.

var leftIndex = function(arr){
   let left = 0;

   for(let i=0;i<m;i++){
      for(let j=0;j<n;j++){
          if(arr[i][j] == 1){
             left = Math.min(j,left);
             break;
           }
       }
   }

   return left;
}

Optimization: O(N+M)

For brute force approach, we were looking for first 1, and used to repeat the same for each row, instead of looking for first 1, how about:
1> looking for first 0 from the right.
2> instead of starting from the end of a row, how about starting from the index from the previous row where 1 occurred. This works since in the question we're given that ow is sorted in ascending order

Let's code it:

var leftIndex = function(arr){
  let row = arr.length;
  let col = arr[0].length;
  let index = -1;
  for(let r=0,c=col-1;r<row && c>=0;){
    if(arr[r][c] == 1){
      index = c;
      c--;
    }else{
      r++;
    }
  }
  return index;
}

Applying Binary Search

Now let's consider a worst-case scenario:

[[0,0,0,0,0,0,0,...... a million 0's ,0,0,0,1,1,1,1],
 [0,0,0,0,1,1,1,...... 1's till the end,1,1,1,1,1,1],
]

Now in such a situation, we will iterate through a million 0's if we apply the previous method. Since we know for a fact that after the first 1, all the following elements will 1. We can use binary search to find the first 0 from right.

So basically we're going to do this :

1> set left pointer to 0 for each row.
2> set right pointer either to max row length or to the index where you saw 1 for the previous row.
3> perform binary search.
4> if the mid for current row equals one, move right pointer, or else move left pointer.
5> set the new index accordingly and continue.

based on our above logic, let's code it :

var leftIndex = function(arr) {
    let m = arr.length;
    let n = arr[0].length;
    let row = 0;
    let col = n;

    let left = 0;
    let right = n;

    while(row<m){
        let left = 0;
        while(left<right){
            let mid = Math.floor((left+right)/2);
            if(arr[mid] == 1){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        col = left;
        row++;
    }

    return col == n? -1 : col;
}

It's all about connecting the dots, there are few basic patterns in computer science and their applications are endless. You've to keep on practicing and go through the process from the brute force in order to connect the dots
That's it! I hope you enjoyed this article! Leave a comment down below if you want me to cover a problem.

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/leftMostColumnIndexOf1.js