NeetCode #295LC-1428MediumBinary Search
← Back to All Problems#295 · #1428 · Leftmost Column with at Least a One(至少有一个 1 的最左端列)
📌 Problem Statement & Constraints
This is an interactive problem. A binary matrix has each row sorted in non-decreasing order.
BinaryMatrix.get(row, col) returns a cell and dimensions() returns [rows, cols]. Return the index of the leftmost column containing at least one 1, or -1. You may call get at most 1000 times. Constraints: 1 <= rows, cols <= 100.💡 Core Algorithmic Approaches
- Binary search each row for its leftmost
1, since the rows are sorted. - Track the global minimum column found so far and use it to shrink the search range for subsequent rows:
hi = best - 1. - If a row's search finds no
1, it contributes nothing. - The shrinking upper bound is what keeps the call count under the budget.
💻 Benchmark Python3 Implementation
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
rows, cols = binaryMatrix.dimensions()
best = cols # sentinel: "not found"
for r in range(rows):
lo, hi = 0, best - 1 # search only left of the current best
while lo < hi:
mid = (lo + hi) // 2
if binaryMatrix.get(r, mid) == 1:
hi = mid # a 1 exists at or left of mid
else:
lo = mid + 1
if lo < cols and binaryMatrix.get(r, lo) == 1:
best = min(best, lo)
return best if best != cols else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(rows * log(cols)) calls to get: about 100 * 7 = 700 calls, within the 1000 budget.
💾 Space Complexity
O(1): a few indices.
⚠️ Interview Pitfalls & Follow-ups
- Scanning each row linearly: O(rows * cols) = 10^4 calls, exceeding the budget.
- Forgetting to shrink
hiwithbest: the call count would still fit here, but the optimisation is the point of the problem. - Using
best - 1whenbest == 0: thenhi = -1and the row search is skipped, which is correct since no column can be left of 0. - Returning
colsinstead of -1: the sentinel must be converted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.