DEV Community

Akhil
Akhil

Posted on • Updated on

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

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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],
]
Enter fullscreen mode Exit fullscreen mode

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.

Alt Text

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (3)

Collapse
 
selvapuram profile image
Madhankumar

@akhilpokle - Awesome explanation. especially the idea of starting the next iteration from the last 1 found.

Collapse
 
akhilpokle profile image
Akhil

Thank you :)

Collapse
 
akhilpokle profile image
Akhil

check this : youtube.com/watch?v=nmaI2RC7SWU

at 14:00 mark.