Leftmost Column with at Least a One
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Brute force: scan every cell from top-left to bottom-right and return the first column index where a 1 appears.
Per-row binary search: since each row is sorted, binary search for the first 1 in each row and take the minimum.
Start from top-right corner: move left when current cell is 1, move down when current cell is 0.
This top-right walk is equivalent to a staircase search and visits at most rows + cols cells.
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.
What Trips People Up in Real Interviews
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).
Solution Code
# """
# 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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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).