Search a 2D Matrix
Problem
m × n integer matrix in which every row is
sorted ascending and each row's first value is larger than the previous row's last value.
Report whether target occurs in the matrix, in O(log(m·n))
time.[[1,3,5,7],[10,11,16,20],
[23,30,34,60]], t=3Outputtruesame matrix, t=13Outputfalse1 ≤ m, n ≤ 100 · -104 ≤ matrix[i][j], target ≤ 104 · Required: O(log(m·n)).
Try it yourself
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
}
}
i to
matrix[i / n][i % n] on the fly.Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.
Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.
Open the Binary Search guide →Approaches
Brute ForceScan Every Cell
O(m · n)Space O(1)Visit each cell with two nested loops and return true on a
match. Uses none of the ordering guarantees.
public boolean searchMatrix(int[][] matrix, int target) { for (int[] row : matrix) { for (int v : row) { if (v == target) return true; } } return false; }
Correct baseline, but throws away all the sortedness.
BetterPick the Row, then Binary Search It
O(m + log n)Space O(1)Because rows don't overlap, target can only live in the row
where row[0] ≤ target ≤ row[n-1]. Find that row with a linear
check of its ends, then binary search inside it.
public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; for (int i = 0; i < m; i++) { if (target < matrix[i][0] || target > matrix[i][n - 1]) continue; int left = 0, right = n - 1; // only this row can hold target while (left <= right) { int mid = left + (right - left) / 2; if (matrix[i][mid] == target) return true; if (matrix[i][mid] < target) left = mid + 1; else right = mid - 1; } return false; } return false; }
Uses sorted rows, but the row lookup is still linear in m.
OptimalBinary Search as a Virtual 1D Array
O(log(m·n))Space O(1)Search indices 0 … m·n-1. Virtual index
mid maps to row mid / n and column
mid % n, so every probe is O(1) and the whole matrix is halved each
step — no copying required.
public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int left = 0, right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; // 1D index -> (row, col) if (val == target) return true; if (val < target) left = mid + 1; else right = mid - 1; } return false; }
One binary search over all cells; meets the required bound.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Scan Every Cell | O(m · n) | O(1) |
| Better | Pick the Row, then Binary Search It | O(m + log n) | O(1) |
| Optimal | Binary Search as a Virtual 1D Array | O(log(m·n)) | O(1) |
- Dividing/modding by
minstead ofn(columns) — wrong cell. - Confusing this with LC 240, where rows don't chain — the 1D trick fails there.
m · ncan overflow for huge matrices — fine here (≤ 104).
- Point out the “first > previous last” rule is what makes it one sorted list.
- Write the index mapping
(r, c) = (i / n, i % n)before coding. - Mention the staircase walk from the top-right (O(m+n)) for the LC 240 variant.