Search a 2D Matrix
Asked at Oracle
Problem
You are given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row. Given a target value, write a function to determine whether the target exists in the matrix. The solution must run in O(log(m * n)) time complexity.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | MEDIUM | View all Oracle questions → |
How to Think About It
Brute force: treat the matrix as a flat array and scan every element one by one — O(m*n) time.
Row-by-row binary search: iterate each row and binary search within it — O(m * log n).
Staircase search: start from top-right corner, move left if target is smaller, down if larger — O(m + n).
Virtual indexing: treat the 2D matrix as a 1D sorted array of length m*n and binary search on it.
Optimal: map a 1D index back to (row, col) via row = mid / n, col = mid % n, then binary search — O(log(m*n)).
Optimal Approach
Flatten the 2D matrix conceptually into a 1D sorted array of length m * n. Perform standard binary search on this virtual 1D array. For any mid index, recover the 2D position using row = mid / n and col = mid % n where n is the number of columns. Compare matrix[row][col] with target and narrow the search window accordingly. This achieves O(log(m * n)) time and O(1) space.
What Trips People Up in Real Interviews
Clarify whether rows and columns are individually sorted or the entire matrix is sorted row-wise.
Confirm the expected time complexity — interviewer usually wants O(log(m*n)), not O(m+n).
Explain how you convert between 1D index and 2D coordinates before coding.
Edge cases: single element matrix, target smaller than first element or larger than last.
Mention that the 1D binary search approach generalizes to any sorted matrix without the first-element-of-row constraint.
Solution Code
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val < target:
lo = mid + 1
else:
hi = mid - 1
return FalseFrequently Asked Questions
What is the Search a 2D Matrix problem?
You are given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row. Given a target value, write a function to determine whether the target exists in the matrix. The solution must run in O(log(m * n)) time complexity.
How do you solve Search a 2D Matrix?
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?
Search a 2D Matrix is asked at Oracle. It is a medium difficulty problem.
What are common mistakes on Search a 2D Matrix?
- Clarify whether rows and columns are individually sorted or the entire matrix is sorted row-wise.
- Confirm the expected time complexity — interviewer usually wants O(log(m*n)), not O(m+n).
- Explain how you convert between 1D index and 2D coordinates before coding.
- Edge cases: single element matrix, target smaller than first element or larger than last.
- Mention that the 1D binary search approach generalizes to any sorted matrix without the first-element-of-row constraint.