You are given an m x n integer matrix with two properties:
- Each row is sorted in non-decreasing order from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if it appears in the matrix, and false otherwise. Aim for O(log(m·n)) time.
Example
3 is in the first row.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Intuition
The simplest approach scans every cell of the matrix, row by row, and returns true the moment it sees the target — false if it finishes without finding it.
function searchMatrix(matrix, target) {
// Look at every cell; the matrix's structure is ignored here.
for (const row of matrix) {
for (const value of row) {
if (value === target) return true;
}
}
return false;
}This is O(m·n) and ignores the strong ordering: each row is sorted, and every row starts above where the previous row ended. Can we do better?
That ordering means the rows, read end to end, form one fully sorted sequence of length m·n. So treat the matrix as a virtual sorted array and run plain binary search over the flat indices 0 … m·n − 1. Map a flat index k back to a cell with matrix[Math.floor(k / n)][k % n] (row = k ÷ n, column = k mod n), and compare as usual. Each step halves the m·n cells, giving O(log(m·n)).
Walking it through over the flattened view:
flattened [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60], target = 16 (3×4 matrix)
Flat index 5 maps to row 1, col 1 (value 11). 11 < 16, so discard the left half.
Now [6, 11], mid = 8 maps to row 2, col 0 (value 23). 23 > 16, so discard the right half.
Flat index 6 maps to row 1, col 2 (value 16) — exactly the target. Found in three steps.
Had we searched 13, no flat index would match and the range would empty out, returning false.
Optimization
Binary search on the flattened index
Because the rows concatenate into one fully sorted sequence, treat the matrix as a virtual array of length m·n and binary-search it. Map a flat index k back to matrix[Math.floor(k/n)][k%n].
O(log(m·n)) time, O(1) space.
function searchMatrix(matrix, target) {
const m = matrix.length;
const n = matrix[0].length;
let lo = 0;
let hi = m * n - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const value = matrix[Math.floor(mid / n)][mid % n];
if (value === target) return true;
if (value < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}Complexity analysis
Time complexity: O(log(m·n)). Here's why:
- The matrix is treated as one sorted sequence of
m·ncells. - Each step maps a flat midpoint back to a cell in O(1) and halves the range.
So the search runs about log₂(m·n) times — overall O(log(m·n)), the same as binary-searching a length-m·n array.
Space complexity: O(1). Here's why:
- Only the flat
lo/hiindices are kept; the matrix isn't flattened into a real array.
The row/column are computed on the fly from the flat index — overall O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| matrix = 2468 | true | Single row, target present. |
| matrix = 2468 | false | Single row, target falls in a gap — absent. |
| matrix = 1 5 9 | true | Single column, target in the last row. |
| matrix = 12 34 | true | Target at the very first cell. |
| matrix = 12 34 | true | Target at the very last cell. |
| matrix = 1020 3040 | false | Target smaller than every cell — absent. |
Try it yourself
Write your solution against the real judge before checking the reference.