Leftmost column index of 1

leftmostCol.js

/*

Leftmost column index of 1
Source: https://leetcode.com/discuss/interview-question/341247/Facebook-and-Google-or-Phone-screen-or-Leftmost-column-index-of-1

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.

Example 1:

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

Input:
[[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]]
Output: -1
Expected solution better than O(r * c).

Implementation is using binary search. Complexity O(row * log(col))
*/

function getLeftMostCol(input) {
	
	// Lets try doing binary search to find the leftmost column.
	var start = 0;
	var end = input[0].length-1;
	while(start<=end) {
		var mid = Math.floor((start+end)/2);
		if(doesColHaveOne(input,mid)) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return start==input[0].length ? -1 : start;
}

function doesColHaveOne(input,col) {
	for(var r=0; r<input.length; r++) {
		if(input[r][col]==1) 
			return true;
	}
	return false;
}

var matrix = [[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 1],
 [0, 0, 0, 0]];

console.log("Expecting 2: ",getLeftMostCol(matrix));

var matrix = [[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 1, 1, 1],
 [0, 0, 0, 0]];
console.log("Expecting 1: ",getLeftMostCol(matrix));

var matrix = [[1, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 1, 1, 1],
 [0, 0, 0, 0]];
console.log("Expecting 0: ",getLeftMostCol(matrix));

var matrix = [[0, 0, 0, 1],
 [0, 0, 0, 1],
 [0, 0, 0, 1],
 [0, 0, 0, 0]];
console.log("Expecting 3: ",getLeftMostCol(matrix));

var matrix = [[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]];
console.log("Expecting -1: ",getLeftMostCol(matrix));