Leftmost Column with at Least a One. Facebook interview question. Thought process from brute force to binary search. 
Tags: javascript, computerscience, career, programming
Published: 2020-04-21 14:37:04

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 : 
```javascript 
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. 

<h3>Brute force: O(M*N)</h3>

A simple brute force solution would be to iterate over each row and find the first index for which array element is 1. 
 
```javascript
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;
}
``` 

<h3>Optimization: O(N+M)</h3>

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

Let's code it:

```javascript
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;
}
```

<h3>Applying Binary Search </h3> 
Now let's consider a worst-case scenario:  
```javascript
[[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 <strong>a million 0's</strong> 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 <strong>binary search</strong> 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](https://dev-to-uploads.s3.amazonaws.com/i/cm1zxsxwgqm55erwff2b.png)

based on our above logic, let's code it : 
```javascript
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 <strong>connect the dots</strong>
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