MediumArrayBinary SearchMatrixInteractiveUpdated Sep 2026

1428. Leftmost Column with at Least a One

Asked at Uber

Difficulty

Medium

Time

O(rows + cols)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given a binary matrix (every cell is 0 or 1) with rows rows and cols columns. Each row is sorted in non-decreasing order, so in every row all the 0s come first and then all the 1s. Find the smallest column index that contains at least one 1. If no column has a 1, return -1.

You cannot read the matrix directly. You may only call two methods of a BinaryMatrix object: dimensions() returns [rows, cols], and get(row, col) returns the value at that cell. Your solution must make at most 1000 calls to get.

The sorted-row rule is the key: once you see a 0 at some column in a row, every cell to its left in that same row is also 0.

Find the first column holding a 1

mat01010011Column 0 has a 1 in row 1, so the answer is 0.
Each row is zeros then ones. We want the smallest column index that has a 1 somewhere in it.

Constraints

  • ●rows == mat.length
  • ●cols == mat[i].length
  • ●1 <= rows, cols <= 100
  • ●mat[i][j] is either 0 or 1
  • ●mat[i] is sorted in non-decreasing order
  • ●At most 1000 calls to BinaryMatrix.get are allowed

Examples

Example 1
Inputmat = [[0,0],[1,1]]
Output0
WhyColumn 0 holds a 1 in the second row, and no column to its left exists, so 0 is the leftmost column with a 1.
Example 2
Inputmat = [[0,0],[0,1]]
Output1
WhyColumn 0 is all zeros. Column 1 has a 1 in the second row, so the answer is 1.
Example 3
Inputmat = [[0,0],[0,0]]
Output-1
WhyThere is no 1 anywhere in the matrix, so we return -1.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Brute force: scan every cell from top-left to bottom-right and return the first column index where a 1 appears.

2

Per-row binary search: since each row is sorted, binary search for the first 1 in each row and take the minimum.

3

Start from top-right corner: move left when current cell is 1, move down when current cell is 0.

4

This top-right walk is equivalent to a staircase search and visits at most rows + cols cells.

5

Optimal is O(rows + cols) with the staircase approach or O(rows * log(cols)) with per-row binary search.

Optimal Approach

Start at the top-right corner (row 0, col cols-1). If the current cell is 1, record the column as a candidate and move left to check for an earlier column. If the current cell is 0, move down to the next row since all cells to the left in this row are also 0. This staircase walk covers at most rows + cols cells and leverages the sorted property of each row. Alternatively, perform a binary search on each row to find the first 1, yielding O(rows * log(cols)) time.

Staircase walk from the top-right corner

mat01010001Start at the top-right cell (row 0, col 1). It is 0,so move down.mat01010001Now (row 1, col 1) is 1, so record col 1 and moveleft.mat01010001(row 1, col 0) is 0, so move down — but we are pastthe last row, so we stop.if get(r,c) == 1: best = c; c -= 1else: r += 1stop when r == rows or c < 0
A 1 means this column is a candidate, so step left. A 0 means the rest of this row is 0, so step down.
ComplexityTime O(rows + cols)Space O(1)The staircase walk moves left or down at every step, so it takes at most rows + cols steps and uses only a few variables.

What Trips People Up in Real Interviews

1

Clarify that the matrix API is interactive and you cannot freely access any cell without using get().

2

Note that rows are sorted 0s then 1s, so the column of the first 1 in each row is a valid binary search target.

3

The top-right starting point is critical: moving left narrows the column when a 1 is found, moving down explores rows below.

4

Track the best answer as you move; each leftward move means you found a better candidate.

5

Edge case: if the matrix contains no 1s at all, return cols (the problem guarantees at least one 1).

Solution Code

O(rows + cols) time
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
#    def get(self, row, col):
#    def dimensions(self):
#

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Leftmost Column with at Least a One problem?

You are given a rows x cols binary matrix where each row is sorted in non-decreasing order. Each row contains only 0s followed by 1s. Find the leftmost column index that contains at least a single 1. You can only access the matrix through a BinaryMatrix.get(row, col) API.

How do you solve Leftmost Column with at Least a One?

The optimal approach runs in O(rows + cols) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Leftmost Column with at Least a One?

Leftmost Column with at Least a One is asked at Uber. It is a medium difficulty problem.

What are common mistakes on Leftmost Column with at Least a One?
  • Clarify that the matrix API is interactive and you cannot freely access any cell without using get().
  • Note that rows are sorted 0s then 1s, so the column of the first 1 in each row is a valid binary search target.
  • The top-right starting point is critical: moving left narrows the column when a 1 is found, moving down explores rows below.
  • Track the best answer as you move; each leftward move means you found a better candidate.
  • Edge case: if the matrix contains no 1s at all, return cols (the problem guarantees at least one 1).