LC: Leftmost Column with at Least a One - spiralgo/algorithms GitHub Wiki

Leftmost Column with at Least a One

The Essence:

The fact that the matrix is row-sorted implies that when a value in some row at some column is 0, then the left-most one in that row can only be found in columns of greater index.

Details:

The information above implies 2 solution ways:

1. The problem-solver can choose the binary search each row to find the first occurrence of 1 and compare the results.
2. When the left-most 1 is found at some index in some row, only indices below that index need to be searched in rows below. This can be put to use to make the search in next rows more efficient.