Search a 2D Matrix II
Asked at Goldman Sachs
Problem
Search a 2D Matrix II asks whether a target exists in a matrix where every row is sorted left to right and every column is sorted top to bottom. Unlike the first version, rows do not continue from one another, so you cannot binary search the matrix as one flat array. The elegant answer walks a staircase from a corner.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
How to Think About It
Brute force scans every cell: O(m * n). Binary searching each row is better at O(m log n), but there is a linear solution.
Key insight: start at the top-right corner. Everything to its left is smaller and everything below it is larger. That single cell lets you discard a whole row or a whole column with one comparison.
If the current value is greater than the target, the entire column below is even larger — move left. If it is smaller, the entire row to the left is even smaller — move down. If equal, you found it.
Walkthrough for target 5 on [[1,4,7,11,15],[2,5,8,12,19],...]: start at 15 -> left to 11 -> left to 7 -> left to 4 -> 4 < 5, down to 5 -> found.
Why not the top-left corner? Both neighbors (right and down) are larger, so a comparison does not tell you which direction to eliminate. The bottom-left corner works just as well as top-right.
Optimal Approach
Step 1: Set r = 0, c = n - 1 (top-right).
Step 2: While r < m and c >= 0:
If matrix[r][c] == target: return true.
If matrix[r][c] > target: c -= 1 (eliminate the column).
Else: r += 1 (eliminate the row).
Step 3: Return false.
Each step removes one row or one column, so there are at most m + n steps.
Time: O(m + n). Space: O(1).
What Trips People Up in Real Interviews
Treating it like Search a 2D Matrix I and binary searching a flattened index. The last value of a row is not guaranteed to be smaller than the first value of the next row here.
Starting from the top-left or bottom-right corner, where both moves go in the same direction and you cannot eliminate anything.
Mixing up the moves. Greater than target means move left (smaller values); less than target means move down (larger values).
Not stating the O(m + n) argument. Explain that every comparison permanently removes a row or column — that is the proof.
Solution Code
def searchMatrix(matrix, target):
m, n = len(matrix), len(matrix[0])
r, c = 0, n - 1
while r < m and c >= 0:
v = matrix[r][c]
if v == target:
return True
if v > target:
c -= 1
else:
r += 1
return FalseFrequently Asked Questions
What is the Search a 2D Matrix II problem?
Search a 2D Matrix II asks whether a target exists in a matrix where every row is sorted left to right and every column is sorted top to bottom. Unlike the first version, rows do not continue from one another, so you cannot binary search the matrix as one flat array. The elegant answer walks a staircase from a corner.
How do you solve Search a 2D Matrix II?
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 Search a 2D Matrix II?
Search a 2D Matrix II is asked at Goldman Sachs. It is a medium difficulty problem.
What are common mistakes on Search a 2D Matrix II?
- Treating it like Search a 2D Matrix I and binary searching a flattened index. The last value of a row is not guaranteed to be smaller than the first value of the next row here.
- Starting from the top-left or bottom-right corner, where both moves go in the same direction and you cannot eliminate anything.
- Mixing up the moves. Greater than target means move left (smaller values); less than target means move down (larger values).
- Not stating the `O(m + n)` argument. Explain that every comparison permanently removes a row or column — that is the proof.