LeetCode 1428 - Leftmost Column with at Least a One

This problem gives us access to a binary matrix where every row is sorted in non-decreasing order. That means every row

leetcodemediumarraybinary-searchmatrixinteractive

LeetCode Problem 1428

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Matrix, Interactive

Solution

Problem Understanding

This problem gives us access to a binary matrix where every row is sorted in non-decreasing order. That means every row looks like some number of 0s followed by some number of 1s. For example:

[0, 0, 0, 1, 1]

is valid, while:

[0, 1, 0, 1]

is not.

The goal is to find the leftmost column index that contains at least one 1. If the matrix contains no 1s at all, we return -1.

The important constraint is that this is an interactive problem. We cannot directly access the matrix. Instead, we interact through the provided BinaryMatrix API:

  • binaryMatrix.get(row, col) retrieves a single value.
  • binaryMatrix.dimensions() returns [rows, cols].

The judge also limits the number of get() calls to at most 1000, so efficiency matters. Even though the matrix dimensions are at most 100 x 100, we should still avoid scanning every cell unnecessarily.

Because every row is sorted, once we encounter a 1 in a row, all elements to its right are also 1. Similarly, if we see a 0, everything to its left is also 0. This ordering property is the key observation that enables an efficient solution.

Several edge cases are important:

  • The matrix may contain only 0s, so the answer should be -1.
  • The leftmost column itself may already contain a 1, so the answer could be 0.
  • A row may contain no 1s at all.
  • A row may contain only 1s.
  • The matrix may have only one row or one column.

The problem guarantees that all rows are sorted, which allows us to use binary search or a smarter traversal strategy.

Approaches

Brute Force Approach

The most straightforward solution is to scan the matrix column by column from left to right. For each column, we check every row to see whether a 1 exists.

The moment we find a 1 in a column, we immediately return that column index because we are scanning from left to right, so it must be the leftmost valid column.

This approach is correct because it explicitly checks every possible candidate column in order. However, it performs many unnecessary API calls. In the worst case, we inspect every cell in the matrix.

With a 100 x 100 matrix, that means up to 10,000 calls to get(), which exceeds the allowed limit of 1000.

Optimal Approach

The key insight comes from the row-sorted property.

We can start at the top-right corner of the matrix:

  • If the current cell is 1, then this column is a valid answer candidate, but there may be an even smaller column index to the left. So we move left.
  • If the current cell is 0, then everything to the left in that row is also 0, so this row cannot help us further. We move down.

This creates a staircase traversal through the matrix.

Because we only move left or down, each row and column is visited at most once. The total number of moves is at most:

rows + cols

which is extremely efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(rows × cols) O(1) Checks every cell column by column
Optimal O(rows + cols) O(1) Uses top-right traversal and matrix ordering

Algorithm Walkthrough

  1. Retrieve the matrix dimensions using binaryMatrix.dimensions().

We need the number of rows and columns before traversal begins. 2. Start from the top-right corner.

Initialize:

  • row = 0
  • col = cols - 1

The top-right corner is useful because it gives us directional information:

  • A 1 means we can move left.
  • A 0 means we must move down.
  1. Maintain a variable to store the current best answer.

Initialize:

answer = -1

If we ever encounter a 1, we update this value. 4. Traverse while we remain inside the matrix.

Continue while:

row < rows and col >= 0
  1. Query the current cell using binaryMatrix.get(row, col).

There are two possibilities:

  • If the value is 1:

  • Record the current column as a candidate answer.

  • Move left because we want a smaller column index.

  • If the value is 0:

  • Move down because all values to the left in this row are also 0.

  1. Return the final answer.

If we never encountered a 1, the answer remains -1.

Why it works

The algorithm relies on the sorted structure of every row.

At any position:

  • If we see a 0, then everything to the left in that row must also be 0, so moving left is pointless. We move down.
  • If we see a 1, then the current column is valid, but there may be another 1 further left. We move left to search for a smaller column index.

Because every move eliminates either one row or one column from consideration, we never revisit cells. The traversal guarantees that the leftmost column containing a 1 will be discovered.

Python Solution

# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
# class BinaryMatrix(object):
#     def get(self, row: int, col: int) -> int:
#     def dimensions(self) -> list[]:

from typing import List

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()

        row = 0
        col = cols - 1

        leftmost_col = -1

        while row < rows and col >= 0:
            if binaryMatrix.get(row, col) == 1:
                leftmost_col = col
                col -= 1
            else:
                row += 1

        return leftmost_col

The implementation begins by retrieving the matrix dimensions. We then initialize the traversal at the top-right corner.

The variable leftmost_col stores the best answer found so far. It starts at -1, which also correctly handles the case where no 1 exists in the matrix.

Inside the loop, each API call determines the next movement direction:

  • A 1 updates the answer and moves left.
  • A 0 moves down.

Because the loop only moves in one of these two directions, the total number of iterations is bounded by rows + cols.

The implementation directly mirrors the staircase traversal explained in the algorithm walkthrough.

Go Solution

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * type BinaryMatrix struct {
 *     Get func(int, int) int
 *     Dimensions func() []int
 * }
 */

func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
    dimensions := binaryMatrix.Dimensions()

    rows := dimensions[0]
    cols := dimensions[1]

    row := 0
    col := cols - 1

    leftmostCol := -1

    for row < rows && col >= 0 {
        if binaryMatrix.Get(row, col) == 1 {
            leftmostCol = col
            col--
        } else {
            row++
        }
    }

    return leftmostCol
}

The Go implementation follows the same logic as the Python version. The main difference is syntax and API access style.

The dimensions are retrieved as a slice, so we access rows and columns using indices 0 and 1.

Go does not require special handling for integer overflow here because all indices remain within matrix bounds.

The traversal logic remains identical, with row++ and col-- controlling movement through the matrix.

Worked Examples

Example 1

mat = [
    [0, 0],
    [1, 1]
]

Expected output:

0

Initial state:

Variable Value
row 0
col 1
answer -1

Step-by-step traversal:

Step Position Value Action New State
1 (0,1) 0 Move down row = 1
2 (1,1) 1 Update answer, move left answer = 1, col = 0
3 (1,0) 1 Update answer, move left answer = 0, col = -1

Loop ends because col < 0.

Final answer:

0

Example 2

mat = [
    [0, 0],
    [0, 1]
]

Expected output:

1

Initial state:

Variable Value
row 0
col 1
answer -1

Traversal:

Step Position Value Action New State
1 (0,1) 0 Move down row = 1
2 (1,1) 1 Update answer, move left answer = 1, col = 0
3 (1,0) 0 Move down row = 2

Loop ends because row == rows.

Final answer:

1

Example 3

mat = [
    [0, 0],
    [0, 0]
]

Expected output:

-1

Traversal:

Step Position Value Action
1 (0,1) 0 Move down
2 (1,1) 0 Move down

We never encounter a 1, so the answer remains -1.

Complexity Analysis

Measure Complexity Explanation
Time O(rows + cols) Each move eliminates one row or one column
Space O(1) Only a few variables are used

The traversal starts at the top-right corner and only moves left or down. Since there are at most rows downward moves and at most cols leftward moves, the total number of iterations is bounded by rows + cols.

No additional data structures are allocated, so the space usage remains constant.

Test Cases

class MockBinaryMatrix:
    def __init__(self, matrix):
        self.matrix = matrix

    def get(self, row, col):
        return self.matrix[row][col]

    def dimensions(self):
        return [len(self.matrix), len(self.matrix[0])]

solution = Solution()

# Example 1
matrix = MockBinaryMatrix([[0, 0], [1, 1]])
assert solution.leftMostColumnWithOne(matrix) == 0  # leftmost column is 0

# Example 2
matrix = MockBinaryMatrix([[0, 0], [0, 1]])
assert solution.leftMostColumnWithOne(matrix) == 1  # only last column contains 1

# Example 3
matrix = MockBinaryMatrix([[0, 0], [0, 0]])
assert solution.leftMostColumnWithOne(matrix) == -1  # no 1 exists

# Single row
matrix = MockBinaryMatrix([[0, 0, 1, 1]])
assert solution.leftMostColumnWithOne(matrix) == 2  # single row traversal

# Single column with 1
matrix = MockBinaryMatrix([[0], [0], [1]])
assert solution.leftMostColumnWithOne(matrix) == 0  # only column contains 1

# Single column with no 1
matrix = MockBinaryMatrix([[0], [0], [0]])
assert solution.leftMostColumnWithOne(matrix) == -1  # all zeros

# All ones
matrix = MockBinaryMatrix([[1, 1], [1, 1]])
assert solution.leftMostColumnWithOne(matrix) == 0  # leftmost possible answer

# Mixed rows
matrix = MockBinaryMatrix([
    [0, 0, 0, 1],
    [0, 1, 1, 1],
    [0, 0, 1, 1]
])
assert solution.leftMostColumnWithOne(matrix) == 1  # middle column is leftmost

# Large zero prefix
matrix = MockBinaryMatrix([
    [0, 0, 0, 0, 1],
    [0, 0, 0, 1, 1],
    [0, 0, 1, 1, 1]
])
assert solution.leftMostColumnWithOne(matrix) == 2  # staircase movement

# Minimum size matrix
matrix = MockBinaryMatrix([[1]])
assert solution.leftMostColumnWithOne(matrix) == 0  # single cell containing 1

Test Summary

Test Why
[[0,0],[1,1]] Basic case where answer is first column
[[0,0],[0,1]] Only last column contains a 1
[[0,0],[0,0]] No valid column exists
Single row Ensures traversal works with one row
Single column with 1 Smallest vertical structure
Single column with no 1 Handles all-zero single column
All ones Confirms algorithm keeps moving left
Mixed rows General realistic scenario
Large zero prefix Verifies staircase traversal
[[1]] Minimum matrix size

Edge Cases

One important edge case occurs when the matrix contains no 1s at all. A naive implementation might incorrectly return 0 or another column index if it does not carefully initialize the answer variable. In this solution, leftmost_col starts as -1 and is only updated when a 1 is actually encountered, so the all-zero case is handled correctly.

Another important edge case is when the very first column already contains a 1. Some implementations stop too early after finding any 1, but that would produce incorrect results because we specifically need the leftmost column. This implementation continues moving left whenever it encounters a 1, guaranteeing that the smallest valid column index is found.

A third edge case involves matrices with only one row or one column. Traversal algorithms sometimes assume both dimensions are larger than one, which can lead to index errors or incorrect loop termination. Here, the loop condition:

while row < rows and col >= 0:

naturally handles these small dimensions without requiring special-case logic.

Another subtle case occurs when some rows contain no 1s while others do. Because the algorithm moves downward after seeing a 0, it correctly skips rows that cannot contribute a better answer, while still exploring rows below that may contain earlier 1s`.