Facebook Pixel

1428. Leftmost Column with at Least a One

MediumArrayBinary SearchInteractiveMatrix
Leetcode Link

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).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 Implementation

1# """
2# This is BinaryMatrix's API interface.
3# You should not implement it, or speculate about its implementation
4# """
5# class BinaryMatrix(object):
6#    def get(self, row: int, col: int) -> int:
7#    def dimensions(self) -> List[int]:
8
9from typing import List
10
11
12class Solution:
13    def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
14        # Get the dimensions of the binary matrix (rows x columns)
15        rows, cols = binaryMatrix.dimensions()
16
17        # Track the overall leftmost column with a 1
18        leftmost_col = -1
19
20        # Iterate through each row to find the leftmost column with a 1
21        for row_idx in range(rows):
22            # Binary search for the first 1 in this row
23            left, right = 0, cols - 1
24            first_one_in_row = -1
25
26            while left <= right:
27                mid = (left + right) // 2
28                # feasible(mid): is there a 1 at this column?
29                if binaryMatrix.get(row_idx, mid) == 1:
30                    first_one_in_row = mid
31                    right = mid - 1  # Search left for earlier 1
32                else:
33                    left = mid + 1  # Search right
34
35            # Update global leftmost if we found a 1 in this row
36            if first_one_in_row != -1:
37                if leftmost_col == -1:
38                    leftmost_col = first_one_in_row
39                else:
40                    leftmost_col = min(leftmost_col, first_one_in_row)
41
42        return leftmost_col
43
1/**
2 * // This is the BinaryMatrix's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * interface BinaryMatrix {
5 *     public int get(int row, int col) {}
6 *     public List<Integer> dimensions {}
7 * };
8 */
9
10class Solution {
11    /**
12     * Finds the leftmost column that contains at least one 1 in a binary matrix.
13     * The matrix rows are sorted in non-decreasing order (0s before 1s).
14     *
15     * @param binaryMatrix The binary matrix to search
16     * @return The index of the leftmost column with a 1, or -1 if no 1 exists
17     */
18    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
19        // Get matrix dimensions
20        List<Integer> dimensions = binaryMatrix.dimensions();
21        int rows = dimensions.get(0);
22        int cols = dimensions.get(1);
23
24        // Track the overall leftmost column with a 1
25        int leftmostColumn = -1;
26
27        // Process each row to find the leftmost 1
28        for (int row = 0; row < rows; row++) {
29            // Binary search for the first occurrence of 1 in current row
30            int left = 0;
31            int right = cols - 1;
32            int firstOneInRow = -1;
33
34            while (left <= right) {
35                int mid = left + (right - left) / 2;
36
37                // feasible(mid): is there a 1 at this column?
38                if (binaryMatrix.get(row, mid) == 1) {
39                    firstOneInRow = mid;
40                    right = mid - 1;  // Search left for earlier 1
41                } else {
42                    left = mid + 1;  // Search right
43                }
44            }
45
46            // Update global leftmost if we found a 1 in this row
47            if (firstOneInRow != -1) {
48                if (leftmostColumn == -1) {
49                    leftmostColumn = firstOneInRow;
50                } else {
51                    leftmostColumn = Math.min(leftmostColumn, firstOneInRow);
52                }
53            }
54        }
55
56        return leftmostColumn;
57    }
58}
59
1/**
2 * // This is the BinaryMatrix's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class BinaryMatrix {
5 *   public:
6 *     int get(int row, int col);
7 *     vector<int> dimensions();
8 * };
9 */
10
11class Solution {
12public:
13    int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
14        // Get matrix dimensions: dimensions[0] = rows, dimensions[1] = columns
15        vector<int> dimensions = binaryMatrix.dimensions();
16        int rowCount = dimensions[0];
17        int colCount = dimensions[1];
18
19        // Track the overall leftmost column with a 1
20        int leftmostColumn = -1;
21
22        // Iterate through each row to find the leftmost 1
23        for (int row = 0; row < rowCount; ++row) {
24            // Binary search for the first occurrence of 1 in current row
25            int left = 0;
26            int right = colCount - 1;
27            int firstOneInRow = -1;
28
29            while (left <= right) {
30                int mid = left + (right - left) / 2;
31
32                // feasible(mid): is there a 1 at this column?
33                if (binaryMatrix.get(row, mid) == 1) {
34                    firstOneInRow = mid;
35                    right = mid - 1;  // Search left for earlier 1
36                } else {
37                    left = mid + 1;  // Search right
38                }
39            }
40
41            // Update global leftmost if we found a 1 in this row
42            if (firstOneInRow != -1) {
43                if (leftmostColumn == -1) {
44                    leftmostColumn = firstOneInRow;
45                } else {
46                    leftmostColumn = min(leftmostColumn, firstOneInRow);
47                }
48            }
49        }
50
51        return leftmostColumn;
52    }
53};
54
1/**
2 * // This is the BinaryMatrix's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class BinaryMatrix {
5 *      get(row: number, col: number): number {}
6 *
7 *      dimensions(): number[] {}
8 * }
9 */
10
11/**
12 * Finds the leftmost column index that contains at least one 1 in a binary matrix.
13 * Each row in the matrix is sorted in non-decreasing order (0s followed by 1s).
14 *
15 * @param binaryMatrix - A binary matrix with sorted rows
16 * @returns The index of the leftmost column containing a 1, or -1 if no such column exists
17 */
18function leftMostColumnWithOne(binaryMatrix: BinaryMatrix): number {
19    // Get matrix dimensions
20    const [rows, cols]: number[] = binaryMatrix.dimensions();
21
22    // Track the overall leftmost column with a 1
23    let leftmostColumn: number = -1;
24
25    // Iterate through each row to find the leftmost 1
26    for (let row: number = 0; row < rows; row++) {
27        // Binary search for the first occurrence of 1 in current row
28        let left: number = 0;
29        let right: number = cols - 1;
30        let firstOneInRow: number = -1;
31
32        while (left <= right) {
33            const mid: number = Math.floor((left + right) / 2);
34
35            // feasible(mid): is there a 1 at this column?
36            if (binaryMatrix.get(row, mid) === 1) {
37                firstOneInRow = mid;
38                right = mid - 1;  // Search left for earlier 1
39            } else {
40                left = mid + 1;  // Search right
41            }
42        }
43
44        // Update global leftmost if we found a 1 in this row
45        if (firstOneInRow !== -1) {
46            if (leftmostColumn === -1) {
47                leftmostColumn = firstOneInRow;
48            } else {
49                leftmostColumn = Math.min(leftmostColumn, firstOneInRow);
50            }
51        }
52    }
53
54    return leftmostColumn;
55}
56

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 leftmostColumn = -1 to track the overall leftmost column where we've found a 1. Starting with -1 indicates no 1 has been found yet.

For each row, we perform binary search using the standard boundary-finding template:

  • Initialize left = 0, right = cols - 1, and firstOneInRow = -1
  • The feasible condition is binaryMatrix.get(row, mid) == 1 — we're looking for the first column where the value is 1
  • Use while left <= right to continue searching until the range is exhausted
  • When we find a 1 at position mid, we record it in firstOneInRow = mid and search left with right = mid - 1 to find an even earlier 1
  • When we find a 0, we search right with left = mid + 1

After each row's binary search, if firstOneInRow != -1, we found a 1 in that row and update our global answer: leftmostColumn = min(leftmostColumn, firstOneInRow).

Finally, we return leftmostColumn directly. If no 1 was found in any row, it remains -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.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

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: rows = 3, cols = 3
  • Set leftmostColumn = -1 (no 1 found yet)

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

  • Initialize: left = 0, right = 2, firstOneInRow = -1
  • Binary search using while left <= right:
    • mid = 1: value is 0 → left = 2
    • mid = 2: value is 1 → firstOneInRow = 2, right = 1
    • left (2) > right (1) → exit loop
  • Found 1 at column 2: leftmostColumn = 2

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

  • Initialize: left = 0, right = 2, firstOneInRow = -1
  • Binary search:
    • mid = 1: value is 1 → firstOneInRow = 1, right = 0
    • mid = 0: value is 0 → left = 1
    • left (1) > right (0) → exit loop
  • Found 1 at column 1: leftmostColumn = min(2, 1) = 1

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

  • Initialize: left = 0, right = 2, firstOneInRow = -1
  • Binary search:
    • mid = 1: value is 0 → left = 2
    • mid = 2: value is 0 → left = 3
    • left (3) > right (2) → exit loop
  • firstOneInRow remains -1 (no 1 found), skip update

Step 5: Return Result

  • Return leftmostColumn = 1

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

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 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 like rows, cols, leftmostColumn, left, right, mid, and firstOneInRow. No additional data structures are created.

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

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using the while left < right with right = mid variant instead of the standard boundary-finding template.

Incorrect Template:

left, right = 0, cols
while left < right:
    mid = (left + right) // 2
    if binaryMatrix.get(row_idx, mid) == 1:
        right = mid  # Wrong! Should use right = mid - 1
    else:
        left = mid + 1
return left  # Wrong! Should track firstTrueIndex

Correct Template:

left, right = 0, cols - 1
first_one_in_row = -1

while left <= right:
    mid = (left + right) // 2
    if binaryMatrix.get(row_idx, mid) == 1:
        first_one_in_row = mid
        right = mid - 1
    else:
        left = mid + 1

Solution: Always use while left <= right, track the answer with firstTrueIndex = -1, and use right = mid - 1 when the feasible condition is true.

2. 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 = -1

    for row_idx in range(rows):
        # Linear search - inefficient!
        for col_idx in range(cols):
            if binaryMatrix.get(row_idx, col_idx) == 1:
                if leftmost_col == -1:
                    leftmost_col = col_idx
                else:
                    leftmost_col = min(leftmost_col, col_idx)
                break

    return leftmost_col

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

3. Not Tracking firstTrueIndex Properly

Some developers return left directly without tracking firstTrueIndex, which can cause issues when no 1 exists in a row.

Incorrect Approach:

left, right = 0, cols - 1
while left <= right:
    mid = (left + right) // 2
    if binaryMatrix.get(row_idx, mid) == 1:
        right = mid - 1
    else:
        left = mid + 1
# Bug: left might be out of bounds or point to a 0
return left

Why it's wrong: When no 1 exists in the row, left will equal cols, which is out of bounds. Always use firstTrueIndex = -1 to explicitly track whether a valid answer was found.

4. Not Handling Edge Cases Properly

Forgetting to handle matrices with no 1s or not checking if firstTrueIndex remains -1.

Incorrect Handling:

# Assuming a 1 always exists
leftmost_col = first_one_in_row  # Bug if first_one_in_row is -1

Solution: Always check if firstTrueIndex != -1 before updating the global answer, and return -1 if no 1 was found in any row.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Recommended Readings

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More