Problem Description

You are given a binary matrix where each element is either 0 or 1. The matrix has a special property: each row is sorted in non-decreasing order (meaning all 0s come before all 1s in each row).

Your task is to find the index of the leftmost column that contains at least one 1. If no column contains a 1, return -1.

The key constraint is that you cannot access the matrix directly. Instead, you must use a BinaryMatrix interface that provides two methods:

• BinaryMatrix.get(row, col) - returns the element at position (row, col)
• BinaryMatrix.dimensions() - returns [rows, cols] representing the matrix dimensions

You are limited to making at most 1000 calls to BinaryMatrix.get().

For example, consider this matrix:

[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 1, 1, 1]]

The leftmost column containing a 1 is column index 1 (the second column), so the answer would be 1.

The solution uses binary search on each row to efficiently find where the first 1 appears in that row. By checking all rows and taking the minimum column index where a 1 is found, we can determine the overall leftmost column with a 1. The bisect_left function performs binary search to find the insertion point for value 1 in each sorted row, which gives us the index of the first 1 (or the length of the row if no 1 exists).

Intuition

Since each row is sorted with all 0s before all 1s, we can think of each row as having a "transition point" where it changes from 0 to 1. Our goal is to find which row has the earliest (leftmost) transition point across the entire matrix.

The naive approach would be to check every element in the matrix starting from the leftmost column and moving right until we find a 1. However, this could require checking many elements, potentially up to m × n in the worst case.

The key insight is that because each row is sorted, we can use binary search within each row to quickly locate where the first 1 appears. Binary search allows us to find this transition point in O(log n) time per row instead of O(n) time.

Think of it this way: for each row, we're asking "at what column index does the first 1 appear?" Binary search is perfect for this because:

1. We're looking for a specific boundary (the change from 0 to 1)
2. The row is sorted, so all 0s are on the left and all 1s are on the right
3. We can check any position and know whether we need to look further left (if we see a 1) or further right (if we see a 0)

By applying binary search to each row independently and keeping track of the minimum column index where we find a 1, we get the overall leftmost column containing a 1. The total number of get() calls becomes O(m × log n), which is much more efficient than a linear search and stays well under the 1000-call limit for reasonable matrix sizes.

The use of bisect_left with a key function elegantly handles the binary search - it finds the leftmost position where 1 would be inserted to maintain sorted order, which is exactly the index of the first 1 in the row (or the row length if no 1 exists).

Learn more about Binary Search patterns.

Solution Approach

The implementation uses binary search to efficiently find the leftmost column containing a 1.

First, we get the matrix dimensions by calling binaryMatrix.dimensions(), which returns [m, n] where m is the number of rows and n is the number of columns.

We initialize a variable ans to n (the total number of columns). This will track the minimum column index where we've found a 1 so far. Starting with n ensures that if no 1 is found in any row, we can detect this condition at the end.

For each row i from 0 to m-1, we perform a binary search to find the column index of the first 1 in that row:

• We use Python's bisect_left function with a custom key function
• bisect_left(range(n), 1, key=lambda k: binaryMatrix.get(i, k)) searches for the leftmost position where value 1 would fit in the sorted sequence
• The range(n) represents column indices from 0 to n-1
• The key function lambda k: binaryMatrix.get(i, k) tells bisect_left to use the actual matrix values for comparison
• This returns the column index j where the first 1 appears in row i (or n if the row contains only 0s)

After finding the position j for each row, we update ans with min(ans, j) to keep track of the overall leftmost column containing a 1.

Finally, we check if ans >= n. If true, it means no 1 was found in any row (all rows returned j = n), so we return -1. Otherwise, we return ans as the leftmost column index containing a 1.

The time complexity is O(m × log n) where we perform binary search (O(log n)) for each of the m rows. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary matrix:

[[0, 0, 1],
 [0, 1, 1],
 [0, 0, 0]]

Step 1: Initialize

• Get dimensions: m = 3 rows, n = 3 columns
• Set ans = 3 (starting with the number of columns)

Step 2: Process Row 0 [0, 0, 1]

• Use binary search to find where the first 1 appears
• Binary search process:
  • Check middle column (col 1): value is 0, so first 1 must be to the right
  • Check between cols 2-2: value at col 2 is 1
  • First 1 is at column index 2
• Update ans = min(3, 2) = 2

Step 3: Process Row 1 [0, 1, 1]

• Binary search to find first 1:
  • Check middle column (col 1): value is 1, so this could be the first 1 or there might be one to the left
  • Check col 0: value is 0
  • First 1 is at column index 1
• Update ans = min(2, 1) = 1

Step 4: Process Row 2 [0, 0, 0]

• Binary search to find first 1:
  • Check middle column (col 1): value is 0, so look right
  • Check col 2: value is 0
  • No 1 found in this row, returns index 3 (equal to n)
• Update ans = min(1, 3) = 1

Step 5: Return Result

• Since ans = 1 < n = 3, we found at least one 1
• Return 1 as the leftmost column containing a 1

The answer is correct: column index 1 is indeed the leftmost column with a 1 (from row 1).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log n), where m is the number of rows and n is the number of columns in the binary matrix. The algorithm iterates through all m rows, and for each row, it performs a binary search using bisect_left to find the leftmost position of 1 in that row. Binary search has a time complexity of O(log n) since it searches through n columns. Therefore, the overall time complexity is O(m × log n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store variables m, n, ans, i, and j. The bisect_left function with the range(n) object and lambda function uses O(1) space since range objects in Python 3 are lazy iterators that don't create the entire list in memory, and the lambda function is evaluated on-demand without storing intermediate results.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Linear Search Instead of Binary Search

A common mistake is scanning each row from left to right to find the first 1, which results in O(m × n) time complexity in the worst case.

Incorrect Approach:

def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
    rows, cols = binaryMatrix.dimensions()
    leftmost_col = cols
  
    for row_idx in range(rows):
        # Linear search - inefficient!
        for col_idx in range(cols):
            if binaryMatrix.get(row_idx, col_idx) == 1:
                leftmost_col = min(leftmost_col, col_idx)
                break  # Found first 1 in this row
  
    return -1 if leftmost_col >= cols else leftmost_col

Solution: Use binary search as shown in the original solution to achieve O(m × log n) complexity.

2. Starting Search from Previously Found Column (Staircase Approach)

While the staircase search pattern (starting from top-right and moving left/down) is actually optimal with O(m + n) complexity, implementing it incorrectly can lead to bugs.

Potential Bug in Staircase Implementation:

def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
    rows, cols = binaryMatrix.dimensions()
    row, col = 0, cols - 1
  
    while row < rows and col >= 0:
        if binaryMatrix.get(row, col) == 1:
            col -= 1  # Move left
        else:
            row += 1  # Move down
  
    # Bug: returning col directly when col might be -1
    return col  # Wrong! Should return col + 1 or handle -1 case

Correct Staircase Solution:

def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
    rows, cols = binaryMatrix.dimensions()
    row, col = 0, cols - 1
  
    while row < rows and col >= 0:
        if binaryMatrix.get(row, col) == 1:
            col -= 1
        else:
            row += 1
  
    return col + 1 if col < cols - 1 else -1

3. Misunderstanding bisect_left Return Value

Some developers might incorrectly validate whether a 1 exists after using bisect_left.

Incorrect Validation:

for row_idx in range(rows):
    first_one_col = bisect_left(
        range(cols), 
        1, 
        key=lambda col_idx: binaryMatrix.get(row_idx, col_idx)
    )
  
    # Unnecessary check - bisect_left already handles this!
    if first_one_col < cols and binaryMatrix.get(row_idx, first_one_col) == 1:
        leftmost_col = min(leftmost_col, first_one_col)

Why it's wrong: bisect_left returns the correct insertion position. If the row contains only 0s, it returns cols (end of range). The additional check wastes API calls and adds unnecessary complexity.

4. Not Handling Edge Cases Properly

Forgetting to handle matrices with no 1s or initializing the result variable incorrectly.

Incorrect Initialization:

leftmost_col = -1  # Wrong initialization!

for row_idx in range(rows):
    first_one_col = bisect_left(...)
    if first_one_col < cols:
        if leftmost_col == -1:
            leftmost_col = first_one_col
        else:
            leftmost_col = min(leftmost_col, first_one_col)

return leftmost_col

Solution: Initialize to cols (as in the original solution) to naturally handle the case where no 1s exist, avoiding special conditional logic.