Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Uber SWE interview with a binary matrix problem. Pretty clean question once you see the trick, but I fumbled around longer than I'd like to admit before getting there.

Questions Asked (1)

Given a binary matrix where every row is sorted in non-decreasing order, find the index of the leftmost column that contains at least one 1. Return -1 if no such column exists.

Algorithms & Data Structures

Author's notes

My first instinct was just brute force every column left to right and scan down.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose an efficient algorithm that leverages the sorted rows. A common optimal approach is to start from the top-right corner and move left or down based on the current value, achieving O(m+n) time. Alternatively, use binary search on each row to find the first 1 and track the minimum column index, which takes O(m log n) time.

Pro tip: Mention the trade-offs between the O(m+n) staircase approach and the O(m log n) binary search approach, and note that the staircase method is optimal when m and n are similar, while binary search may be better if n is much larger than m. Also, discuss how to handle large matrices that don't fit in memory, showing awareness of scalability.

1. Clarify the problem

Ask about matrix dimensions, whether rows can be empty, and if the matrix is sorted row-wise only or also column-wise. Confirm the definition of 'leftmost column' and the return value when no 1 exists.

2. Discuss brute force and its complexity

Mention that scanning all columns from left to right and checking each row would be O(m*n) time, which is inefficient. This sets the stage for optimization.

3. Propose an optimized approach

Describe the staircase method: start at the top-right corner. If the current cell is 1, update the answer and move left; if 0, move down. This finds the leftmost column with a 1 in O(m+n) time.

4. Analyze time and space complexity

Explain that the staircase method uses O(1) extra space and O(m+n) time. Compare with binary search per row (O(m log n)) and justify why the staircase is optimal for this problem.

5. Handle edge cases and test

Walk through examples: all zeros, all ones, single row/column, and matrices where the leftmost 1 is in the first column. Verify the algorithm returns -1 when no 1 exists.

Key Points to Mention

Leveraging the sorted property of each row to avoid scanning all elements.
The staircase traversal from top-right corner, moving left on 1 and down on 0.
Time complexity O(m+n) and space complexity O(1) for the optimal solution.
Alternative approach using binary search on each row to find the first 1, with O(m log n) time.
Handling edge cases such as empty matrix, no 1s, and multiple 1s in the same column.
Potential follow-up: what if the matrix is sorted both row-wise and column-wise? (Then binary search on the first row or staircase still works.)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.