#74
Search a 2D Matrix
Medium Binary search on flattened index
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each row is sorted and each row starts with a value larger than the previous row's last value. Decide if target is in the matrix in O(log(m·n)).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: find a value in a matrix that is sorted row after row.
Why this works: read row by row it's one sorted list, so binary search over index k = r·n + c.
Example: target 3 in [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
mid index 5 → (1,1) = 11 > 3 → leftmid index 2 → (0,2) = 5 > 3 → leftmid index 0 → 1 < 3 → right; index 1 → 3 ✓
✦Hints open one at a time
Read row by row, the matrix is one sorted list of m·n numbers.
Index k in that list is matrix[k / n][k % n].
↗Approach
Binary search over 0..m·n−1, converting each mid to row and column.
</>Solution (Java)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = matrix[mid / n][mid % n]; // flattened index -> cell
if (v == target) return true;
if (v < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
}!Common mistake
Using k / m and k % m — divide by the number of columns, n.
Complexity
- Time: O(log(m·n)).
- Space: O(1).
Topic: 2D Arrays & Matrix
🎬 Episode 14: video coming soon