Search a 2D Matrix II
Decide whether a target is in a grid whose rows and columns are each sorted in ascending order, in O(rows + columns), by walking from the top-right corner.
Updated Long read: 9 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Check every cell | O(rows × columns) | O(1) |
| Binary search each row | O(rows × log columns) | O(1) |
| Staircase walk from the top-right | O(rows + columns) | O(1) |
The problem
You are given a grid of integers and a target. Every row of the grid is sorted in ascending order from left to right, and every column is sorted in ascending order from top to bottom. Return true if the target appears anywhere in the grid, and false if it does not.
grid =
1 3 6 10 15
2 5 9 14 19
4 8 13 18 22
7 12 17 21 24
target = 8 → true
target = 11 → false
target = 30 → false (larger than everything)Notice what is not promised. A row does not have to start above the end of the previous row: the second row begins with 2, which is smaller than most of the first row. So the grid cannot be read row by row as one sorted list, and a single binary search over the whole thing is not available.
Approach 1: check every cell
Look at each cell in turn and stop at the first match.
JavaScript
function searchMatrixBruteForce(grid, target) {
for (const row of grid) {
for (const value of row) {
if (value === target) return true;
}
}
return false;
}Python
def search_matrix_brute_force(grid, target):
for row in grid:
for value in row:
if value == target:
return True
return FalseTime O(rows × columns). Space O(1). It would work just as well on a grid in no order at all, which is a sign that it is wasting information.
Approach 2: binary search each row
Each row on its own is a sorted list, so each row can be binary searched. This is the exact-value template from the binary search pattern, run once per row.
JavaScript
function rowContains(row, target) {
let lo = 0;
let hi = row.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (row[mid] === target) return true;
if (row[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}
function searchMatrixByRows(grid, target) {
for (const row of grid) {
if (rowContains(row, target)) return true;
}
return false;
}Python
def row_contains(row, target):
lo = 0
hi = len(row) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if row[mid] == target:
return True
if row[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return False
def search_matrix_by_rows(grid, target):
for row in grid:
if row_contains(row, target):
return True
return FalseTime O(rows × log columns). Space O(1). A clear improvement, but it treats the rows as unrelated lists. The column ordering, half of what the problem gives you, goes unused.
Finding a cell that can rule out a whole line
To use both orderings, look for a cell where a single comparison is guaranteed to discard something big.
Take the top-right cell, 15 in the example. It is the largest value in its row, because everything else in the row is to its left. It is the smallest value in its column, because everything else in the column is below it. So:
- If the target is smaller than this cell, it is smaller than everything in the column. The column can be crossed out.
- If the target is larger than this cell, it is larger than everything in the row. The row can be crossed out.
Either way, what remains is a smaller grid with the same sorted property, and its top-right cell can be asked the same question.
The top-left cell cannot do this. It is the smallest in both its row and its column, so a larger target could still be anywhere. The bottom-right has the mirror-image problem. Only the top-right and bottom-left corners sit at the largest end of one line and the smallest end of the other.
Approach 3: staircase walk from the top-right
JavaScript
function searchMatrixStaircase(grid, target) {
if (grid.length === 0) return false;
let row = 0;
let col = grid[0].length - 1;
while (row < grid.length && col >= 0) {
const value = grid[row][col];
if (value === target) return true;
if (value > target) {
col--; // everything below in this column is larger still
} else {
row++; // everything to the left in this row is smaller still
}
}
return false;
}Python
def search_matrix_staircase(grid, target):
if not grid:
return False
row = 0
col = len(grid[0]) - 1
while row < len(grid) and col >= 0:
value = grid[row][col]
if value == target:
return True
if value > target:
col -= 1 # everything below in this column is larger still
else:
row += 1 # everything to the left in this row is smaller still
return Falserow and col mark the top-right corner of the part of the grid that has not been ruled out. The loop ends when that part has no rows or no columns left.
Walkthrough
The grid from the top of the page, target = 8:
| row | col | Value | Compare with 8 | Action |
|---|---|---|---|---|
| 0 | 4 | 15 | Larger | Cross out column 4, move left |
| 0 | 3 | 10 | Larger | Cross out column 3, move left |
| 0 | 2 | 6 | Smaller | Cross out row 0, move down |
| 1 | 2 | 9 | Larger | Cross out column 2, move left |
| 1 | 1 | 5 | Smaller | Cross out row 1, move down |
| 2 | 1 | 8 | Equal | Return true |
The path drawn on the grid:
1 3 6 ← 10 ← 15
↓
2 5 ← 9 14 19
↓
4 [8] 13 18 22
7 12 17 21 24And target = 11, which is absent:
| row | col | Value | Compare with 11 | Action |
|---|---|---|---|---|
| 0 | 4 | 15 | Larger | Move left |
| 0 | 3 | 10 | Smaller | Move down |
| 1 | 3 | 14 | Larger | Move left |
| 1 | 2 | 9 | Smaller | Move down |
| 2 | 2 | 13 | Larger | Move left |
| 2 | 1 | 8 | Smaller | Move down |
| 3 | 1 | 12 | Larger | Move left |
| 3 | 0 | 7 | Smaller | Move down |
| 4 | 0 | row is off the grid: return false |
Eight cells read out of twenty to prove that 11 is nowhere in the grid. Every step removes one row or one column and none ever comes back, so the walk takes at most rows + columns steps.
Time O(rows + columns). Space O(1).
Why the walk cannot miss the target
It is fair to wonder whether moving only left and down could step around the target. It cannot, because nothing is ever discarded without proof. A column is crossed out only when its smallest remaining value (the one at the current row) is already larger than the target. A row is crossed out only when its largest remaining value (the one at the current column) is already smaller than the target. If the target is in the grid, its cell is never in a crossed-out line, so it stays inside the shrinking region until the walk lands on it.
Comparing the approaches
| Approach | Uses row order | Uses column order | Time | Comparisons on a 1,000 × 1,000 grid, at most |
|---|---|---|---|---|
| Check every cell | No | No | O(rows × columns) | 1,000,000 |
| Binary search each row | Yes | No | O(rows × log columns) | About 10,000 |
| Staircase walk | Yes | Yes | O(rows + columns) | 2,000 |
All three need O(1) extra space. The staircase is also the shortest of the two fast versions to write, with no midpoint arithmetic to get wrong.
If the grid were fully sorted, with each row starting above the end of the one before, a single binary search over all the cells would do better still at O(log(rows × columns)). The matrix search pattern shows that version and how to tell the two kinds of grid apart. The same walk, adapted to count cells instead of looking for one, solves Count Negative Numbers in a Sorted Matrix and is the engine inside Kth Smallest Element in a Sorted Matrix.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
const grid = [[1, 3, 6, 10, 15], [2, 5, 9, 14, 19], [4, 8, 13, 18, 22], [7, 12, 17, 21, 24]];
console.log(searchMatrixStaircase(grid, 8)); // true
console.log(searchMatrixStaircase(grid, 11)); // false
console.log(searchMatrixStaircase(grid, 30)); // false
console.log(searchMatrixByRows(grid, 21)); // truePython
grid = [[1, 3, 6, 10, 15], [2, 5, 9, 14, 19], [4, 8, 13, 18, 22], [7, 12, 17, 21, 24]]
print(search_matrix_staircase(grid, 8)) # True
print(search_matrix_staircase(grid, 11)) # False
print(search_matrix_staircase(grid, 30)) # False
print(search_matrix_by_rows(grid, 21)) # TrueThe comment after each line is the result you should see.
Common mistakes
- Treating the grid as one sorted list. Converting a single index into a row and a column and binary searching only works when each row starts above the end of the previous one. This problem does not promise that.
- Starting at the top-left or bottom-right. From those corners a comparison cannot choose between the two moves.
- Moving left and down in the same step. A diagonal move discards a row and a column on the evidence for only one of them, and can jump straight over the target.
- Swapping the two moves. Larger than the target means move left; smaller means move down. Getting them the wrong way round walks off the grid at once and returns
falsefor almost everything. - Reading
grid[0]of an empty grid. If the grid may have no rows, check for that before working out the starting column.
Original problem: LeetCode 240: Search a 2D Matrix II