⚡Flashcard Drill➔
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

  1. Binary search each row for its leftmost 1, since the rows are sorted.
  2. Track the global minimum column found so far and use it to shrink the search range for subsequent rows: hi = best - 1.
  3. If a row's search finds no 1, it contributes nothing.
  4. 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 hi with best: the call count would still fit here, but the optimisation is the point of the problem.
  • Using best - 1 when best == 0: then hi = -1 and the row search is skipped, which is correct since no column can be left of 0.
  • Returning cols instead 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems