622. Leftmost Column with at Least a One
You are given a binary matrix mat (every entry is 0 or 1) with a special structure: each row is sorted in non-decreasing order, meaning all of a row's 0s come before all of its 1s.
The function receives mat and returns the index (0-based) of the leftmost column that contains a 1 in any row. If the matrix holds no 1 at all, return -1.
In the interview version of this problem the matrix hides behind a rate-limited API, so aim for a solution that inspects far fewer than all n × m cells — the row-sorted guarantee is there to be exploited.
Example 1:
Input: mat = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]
Output: 1
Explanation: Row 2 is the first to switch to 1s, at column 1. No row has a 1 any further left, so the answer is 1.
Example 2:
Input: mat = [[0, 0], [0, 0]]
Output: -1
Explanation: The matrix contains no 1 anywhere, so the answer is -1.
Constraints:
- 1 ≤ n, m ≤ 100
- mat[i][j] is 0 or 1
- Every row is sorted in non-decreasing order (all 0s, then all 1s)
Hints:
Within one row, "where does the first 1 start?" is a classic lower-bound question on a sorted 0/1 sequence — binary search answers it in O(log m). Doing that for every row already beats scanning.
Can rows share work? Once some row proves column c contains a 1, no column right of c matters for any other row.
Start at the top-right corner. On a 1, move left (a better column might exist in this row); on a 0, move down (this row's 1s start further right, and rows above are done). Each step discards a row or a column — O(n + m) total.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: mat = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]]
Expected output: 1