Matrix Search
Search a grid with sorted rows and columns: binary search a fully sorted grid, walk a staircase from the top-right corner, or count to find a value by rank.
Matrix search is a set of techniques for finding a value in a grid of numbers whose rows and columns are sorted, without looking at every cell. Each comparison rules out a whole row, a whole column or half the grid.
The idea
Picture a seating plan where people get taller as you move right along any row and taller as you move down any column. To find someone of a given height, you would not measure everybody. Stand at the top-right seat. That person is the tallest in their row and the shortest in their column. If they are too tall, nobody below them can be right either, so the whole column is out. If they are too short, nobody to their left can be right, so the whole row is out. One question, one line of seats dismissed.
That is the heart of the pattern: in a sorted grid, one cell tells you something about every cell in a line with it. How much it tells you depends on how strictly the grid is sorted, so the first job is always to read the problem and work out which kind of grid you have.
Two kinds of sorted grid
Fully sorted Sorted by row and by column
(reads like one long list) (each line is sorted on its own)
3 6 8 10 2 5 9 14
13 17 21 24 4 8 12 17
29 30 36 41 7 11 15 20
10 13 18 23In the grid on the left, each row is sorted and every row starts with a value larger than the end of the row before it. Read it row by row and you get one sorted list.
In the grid on the right, each row is sorted and each column is sorted, but the rows overlap: the second row starts at 4, which is smaller than the 14 that ends the first row. Reading it row by row does not give a sorted list.
Every fully sorted grid is also sorted by row and by column, so the techniques for the looser kind work on both. The reverse is not true.
When to use it
- The input is a grid, and the problem says its rows, its columns or both are sorted.
- You need to know whether a value is present, how many cells are on one side of a threshold, or which value has a given rank.
- The problem hints that visiting every cell is too slow.
Technique 1: treat a fully sorted grid as one list
When the grid is fully sorted, do not write anything clever. Number the cells 0, 1, 2 and so on in reading order, run an ordinary binary search over those numbers, and convert a number back to a row and a column only when you need to look at a cell.
With cols columns, cell number i is in row Math.floor(i / cols) and column i % cols.
function searchSortedGrid(grid, target) {
if (grid.length === 0) return false;
const cols = grid[0].length;
let lo = 0;
let hi = grid.length * cols - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
const value = grid[Math.floor(mid / cols)][mid % cols];
if (value === target) return true;
if (value < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}Walkthrough
Searching the fully sorted grid above for 21. It has 3 rows of 4, so the cells are numbered 0 to 11.
| lo | hi | mid | Row, column | Value | Action |
|---|---|---|---|---|---|
| 0 | 11 | 5 | 1, 1 | 17 | Smaller than 21: lo = 6 |
| 6 | 11 | 8 | 2, 0 | 29 | Larger than 21: hi = 7 |
| 6 | 7 | 6 | 1, 2 | 21 | Found |
Three looks at twelve cells. The cost is O(log(rows × columns)) time and O(1) space.
Do not use this on a grid that is only sorted by row and by column. The numbering would not be in order, and binary search on data that is not in order gives wrong answers without any warning.
Technique 2: the staircase walk
For a grid sorted by row and by column, start at the top-right corner and repeat one comparison:
- The cell equals the target: found.
- The cell is larger than the target: everything below it in this column is larger still. Move one column left.
- The cell is smaller than the target: everything to its left in this row is smaller still. Move one row down.
Stop when you step off the grid. The path only ever goes left or down, which is where the staircase name comes from.
// Returns [row, column] of the target, or null when it is absent.
function staircaseSearch(grid, target) {
if (grid.length === 0) return null;
let row = 0;
let col = grid[0].length - 1;
while (row < grid.length && col >= 0) {
const value = grid[row][col];
if (value === target) return [row, col];
if (value > target) {
col--; // this column, from here down, is too large
} else {
row++; // this row, from here leftwards, is too small
}
}
return null;
}Walkthrough
Searching the second grid above for 11:
| Row | Column | Value | Compare with 11 | Action |
|---|---|---|---|---|
| 0 | 3 | 14 | Larger | Drop column 3: move left |
| 0 | 2 | 9 | Smaller | Drop row 0: move down |
| 1 | 2 | 12 | Larger | Drop column 2: move left |
| 1 | 1 | 8 | Smaller | Drop row 1: move down |
| 2 | 1 | 11 | Equal | Return [2, 1] |
2 5 9 ← 14
↓
4 8 ← 12 17
↓
7 [11] 15 20
10 13 18 23Each step removes a row or a column for good, and there are only rows rows and columns columns to remove, so the walk takes at most rows + columns steps: O(rows + columns) time and O(1) space. On a 1,000 by 1,000 grid that is at most 2,000 comparisons instead of 1,000,000.
Why the top-right corner
The starting corner has to be a cell where the two possible moves lead to opposite kinds of value. At the top-right, moving left gives smaller values and moving down gives larger ones, so "too large" and "too small" each have exactly one sensible response.
The bottom-left corner has the same property and works just as well, with the moves mirrored (up for smaller, right for larger). The top-left corner does not work: it is the smallest value in both its row and its column, so when the target is larger there is no way to tell whether to go right or down. The bottom-right fails for the same reason in reverse.
Technique 3: count with the staircase
The same walk can answer a different question: how many cells are less than or equal to some value? Because each row is sorted, the cells that qualify in a row form a block at its left end. Because each column is sorted, that block can only stay the same or shrink as you go down. So the boundary between "small enough" and "too large" is itself a staircase, and one walk along it counts every qualifying cell.
// How many cells hold a value less than or equal to limit.
function staircaseCount(grid, limit) {
if (grid.length === 0) return 0;
let col = grid[0].length - 1;
let count = 0;
for (let row = 0; row < grid.length; row++) {
while (col >= 0 && grid[row][col] > limit) col--;
count += col + 1; // columns 0..col of this row qualify
}
return count;
}col never moves back to the right, so across the whole loop it moves at most columns times: still O(rows + columns).
Counting the cells of the second grid that are at most 12:
| Row | Row values | col settles at | Added | Running count |
|---|---|---|---|---|
| 0 | 2, 5, 9, 14 | 2 | 3 | 3 |
| 1 | 4, 8, 12, 17 | 2 | 3 | 6 |
| 2 | 7, 11, 15, 20 | 1 | 2 | 8 |
| 3 | 10, 13, 18, 23 | 0 | 1 | 9 |
From a count to a rank
A fast count turns "what is the k-th smallest value?" into a search for a number instead of a search for a cell. Try a candidate value. If at least k cells are less than or equal to it, the answer is that candidate or something smaller. If fewer than k are, the answer is larger. That yes-or-no test flips exactly once as the candidate grows, which is all binary search on the answer needs.
// The k-th smallest value in the grid, counting from k = 1.
function gridValueAtRank(grid, k) {
let lo = grid[0][0]; // smallest value
let hi = grid[grid.length - 1][grid[0].length - 1]; // largest value
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (staircaseCount(grid, mid) >= k) {
hi = mid; // mid is big enough: it may be the answer
} else {
lo = mid + 1; // too few cells at or below mid
}
}
return lo;
}The search runs over the range of values, from the smallest to the largest, and each step costs one staircase count. That makes it O((rows + columns) × log(max − min)) time and O(1) space. The candidate in the middle is often a number that is not in the grid at all. That is fine: the loop ends on the smallest number with at least k cells at or below it, and that number is always a real cell value. Kth Smallest Element in a Sorted Matrix works through why.
Choosing a technique
| The grid is | You need | Technique | Time |
|---|---|---|---|
| Fully sorted | Whether a value is present | 1: binary search over cell numbers | O(log(rows × columns)) |
| Sorted by row and by column | Whether a value is present | 2: staircase walk | O(rows + columns) |
| Sorted by row and by column | How many cells pass a threshold | 3: staircase count | O(rows + columns) |
| Sorted by row and by column | The value with a given rank | 3: staircase count inside a binary search on the value | O((rows + columns) × log(max − min)) |
| Sorted by row only | Whether a value is present | Binary search each row in turn | O(rows × log columns) |
Looking at every cell costs O(rows × columns) and is the baseline all of these improve on.
Complexity
- Time: logarithmic in the number of cells for a fully sorted grid; O(rows + columns) for a staircase walk or count.
- Space: O(1) for all three. Only a row, a column and a counter are kept.
Common mistakes
- Binary searching cell numbers in a grid that is not fully sorted. Check that each row really does start above the end of the previous one.
- Starting the staircase at the top-left or bottom-right. From those corners both moves go the same way, so a comparison cannot choose between them.
- Moving diagonally. Stepping left and down at once can jump over the target. Each comparison earns exactly one move.
- Mixing up rows and columns in the conversion. Divide and take the remainder by the number of columns, not rows. A square test grid hides this bug; test with a grid that is wider than it is tall.
- Forgetting the grid may be sorted in descending order. The walk still works, but the meaning of each move flips. Work out afresh what "too large" lets you discard.
- Resetting the column for every row when counting. That turns an O(rows + columns) count back into O(rows × columns).
Practise
- Count Negative Numbers in a Sorted Matrix (easy): a staircase count on a grid sorted in descending order.
- Search a 2D Matrix II (medium): the staircase walk itself.
- Kth Smallest Element in a Sorted Matrix (hard): a staircase count inside a binary search on the value.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Count Negative Numbers in a Sorted Matrix | easy | O(rows + columns) | O(1) | Medium read: 8 min |
| Search a 2D Matrix II | medium | O(rows + columns) | O(1) | Long read: 9 min |
| Kth Smallest Element in a Sorted Matrix | hard | O(n log(max − min)) | O(1) | Long read: 11 min |