Where it runs
1. The problem
You have a grid of numbers, and the numbers in it are in order. In every row they grow from left to right. In every column they grow from top to bottom. You are given a target number and must answer one question: is it in the grid or not?
The simplest way is to look at every cell. In a big grid that is slow. The order of the numbers lets you skip almost every cell and reach the answer along one short path.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedsearchMatrix([[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], 14)| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 4 | 7 | 11 | 15 |
| 1 | 2 | 5 | 8 | 12 | 19 |
| 2 | 3 | 6 | 9 | 16 | 22 |
| 3 | 10 | 13 | 14 | 17 | 24 |
| 4 | 18 | 21 | 23 | 26 | 30 |
Is 14 in the matrix? Start at the top-right corner: everything to its left is smaller, everything below it is larger.
Bars: the 48 cells of the grid laid out row after row; every row and every column grows. The target is in the bottom row. In the size table n is the number of cells in a square grid.
One operation is one cell checked. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(m·n)O(m + n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- matrix sorted along both rows and columns
- search for a value in a 2D sorted grid
- start from a corner and eliminate a row or column
- row and column both monotonic
Looks similar, isn't
- Binary search (array)
When each row continues the last, the grid is one sorted list. A plain binary search then works.
- Two pointers (opposite ends)
The staircase walk is that idea in two dimensions. Exactly one index moves per step.
- Matrix traversal (spiral / diagonal)
That visits every cell in a chosen order. Here most cells are never read at all.
- Linear search
A scan works and costs O(rc). The sorted structure is what makes it wasteful.
An r by c grid gives O(r + c) for the staircase walk. A fully sorted grid allows O(log rc).
On LeetCode
Problems on a grid whose rows and columns are both sorted, asking whether a value is there or how many values sit below some line. Start at the top-right corner, and each comparison drops a row or a column, O(rows + cols).
The lesson task, word for word.
Rows and columns both go down, so start at the top-right, step left while the value is negative, and add the negatives to your right for each row.
Each row starts above the previous row's end, so the corner walk works, and a binary search over all cells as one sorted list is faster.
Binary search on the value, and for each guess count the cells at or below it with the corner walk in O(n).