Staircase search in a sorted grid
Search a grid whose rows and columns are both sorted by starting at the top-right corner and stepping left or down.
O(rows + cols)Space O(1)3 practice problemsStep-through pictureThe idea
Picture a grid of numbers where every row goes up from left to right, and every column goes up from top to bottom. You want to know if a value is in it. Checking every cell works but is slow. Binary search on each row is better. There is a simpler trick that is faster still.
Start at the top-right corner. That cell is special: it is the biggest in its row and the smallest in its column. If it is bigger than the target, the whole column below it is even bigger, so that column can't hold the target: step left. If it is smaller, the whole row to its left is even smaller: step down.
Every step removes a full row or a full column. In a grid with rows rows and cols columns, you take at most rows + cols steps. The path looks like a staircase going down and to the left.
An everyday example
Finding a shirt on a sorted rack
A store hangs shirts in a grid: each row is a color from light to dark, and each column is a size from small to large, with prices rising both ways. You want a shirt that costs exactly 30. You start at the top-right shirt. It costs 45, too much, and every shirt below it costs even more, so you ignore that column and step left. The next one costs 20, too little, and everything to its left in that row is cheaper, so you step down. Each look rules out a whole row or column.
| In the example | In the code |
|---|---|
| The rack of shirts | The 2D array grid |
| Starting at the top-right shirt | row = 0, col = grid[0].length - 1 |
| Too expensive: ignore this column | col-- |
| Too cheap: ignore this row | row++ |
| Walking off the rack | row === grid.length or col < 0: not found |
From the slow way to staircase search in a sorted grid
- The obvious way checks every cell:
rows × colschecks, a million for a 1,000 by 1,000 grid. That ignores all the order. A better first idea is binary search on each row, which costs aboutrows × log₂ cols, around 10,000 checks for the same grid. It uses the row order but still ignores the column order. - Look for a cell that can rule out a whole line with one check. A cell in the middle can't: if it is too small, the target could be to its right or below it. The top-left cell has the same problem. But the top-right cell is the largest in its row and the smallest in its column, so its two directions point opposite ways, and that is exactly what makes a decision possible.
- If the top-right cell is bigger than the target, everything below it in its column is bigger still, so that whole column is out: step left. If it is smaller, everything to its left in its row is smaller still, so that whole row is out: step down. Either way, what is left is a smaller grid, and you are standing on its top-right corner again.
- Each step removes one row or one column, and there are only
rows + colsof them, so the walk takes at mostrows + cols - 1checks, under 2,000 for the 1,000 by 1,000 grid. Start top-right, step left when too big, step down when too small, stop when found or off the grid: that loop is staircase search.
How it works
- Start at the top-right cell:
row = 0andcolset to the last column. - Read
value = grid[row][col]. - If
valueequalstarget, return[row, col]. - If
valueis bigger thantarget, every cell below it in this column is bigger too, so step left:col--. - If
valueis smaller, every cell to its left in this row is smaller too, so step down:row++. - If you step off the grid, the target is not in it: return
[-1, -1].
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function staircaseSearch(grid, target) {if (grid.length === 0) return [-1, -1];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--;} else {row++;}}return [-1, -1];}
How fast it is
| Time | O(rows + cols) |
|---|---|
| Extra memory | O(1) |
Each step removes one row or one column, and there are rows + cols of them. Only the current position is stored.
- Best case
O(1)The target is the top-right cell,
grid[0][cols - 1], so the first check finds it. - Average case
O(rows + cols)A random target usually sits somewhere in the middle, so the walk crosses a good part of the grid, one row or column at a time.
- Worst case
O(rows + cols)The target is missing or near the bottom-left corner: up to
rows + cols - 1checks, 7 for the 4 by 4 trace.
Common mistakes
- Starting at the top-left corner. That cell is the smallest in both its row and column, so if it is too small you can't tell whether to go right or down.
- Using this on a grid where only the rows are sorted. Then the column rule is false and the walk can step past the target.
- Reading
grid[0].lengthon an empty grid, which throws an error. Checkgrid.lengthfirst. - Treating a grid whose rows continue into each other (each row starts after the previous one ends) with this walk. It works, but plain binary search over all cells is faster there:
O(log(rows × cols)).
When to use it
Look for these clues in a problem:
- A 2D grid where each row is sorted and each column is sorted.
- You need to find a value, or count how many cells are below some limit.
- The grid is too big to check every cell, and rows do not continue into each other (so it is not one long sorted list).
Check yourself
Answer each one in your head first, then open it.
Why can't the walk start at the top-left corner?
That cell is the smallest in both its row and its column. If it is too small, the target could be to the right or below, so no row or column can be ruled out.
What is the largest number of checks the walk can make on a 5 by 8 grid?
5 + 8 - 1 = 12. Each check removes a row or a column, and the walk ends once all rows or all columns are gone.
Does the walk need each row to continue where the previous row ended?
No. It only needs each row and each column to be sorted on its own. In the trace's grid, 10 starts the last row while 11 sits in the first row, and the walk is still correct.
What breaks if the columns are not sorted?
Stepping left after a too-big value is no longer safe: a smaller cell, maybe the target, could sit below it in the same column. The walk can then miss the target.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The walk keeps one promise: if target is in the grid, it is in the part from row row downward and from column col leftward. At the start that part is the whole grid, so the promise holds.
Each step keeps it. If value > target, every cell below it in column col is at least value, because columns are sorted, so none of them can be the target, and dropping the column with col-- is safe. If value < target, every cell to its left in row row is at most value, because rows are sorted, so dropping the row with row++ is safe.
Each check drops one row or one column, so after at most rows + cols - 1 checks either all rows or all columns are gone, and the loop condition fails. By the promise, an empty part means the target is nowhere in the grid, so returning [-1, -1] is correct.
Going deeper
3 more ideas
Why the corner cell decides everything
The top-right cell of the part still being searched is the largest in its row and the smallest in its column. So comparing it with the target always rules out something. If it is too big, everything below it is even bigger. If it is too small, everything left of it is even smaller. The cells that remain always form a smaller rectangle with a new top-right corner.
How long it takes
Each step either moves down a row or left a column, never back. There are rows rows and cols columns, so there are at most rows + cols steps. That is O(rows + cols), much better than checking all rows × cols cells.
Counting instead of finding
The same walk counts cells that are at most limit. Start at the bottom-left instead. If the cell is <= limit, every cell above it in that column is too, so add row + 1 to the count and step right. Otherwise step up. This count is the key step for finding the k-th smallest value in such a grid.
Work it by hand
Every step in a table, with why
Look for 13 in a 4 by 4 grid whose rows and columns are both sorted. It isn't there, so the walk goes all the way off the grid.
grid = [[2, 6, 11, 18], [4, 9, 14, 21], [7, 12, 19, 25], [10, 16, 23, 30]], target = 13
| Step | row | col | value | What happens | Why |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 18 | 18 > 13, so col-- | Start at the top-right corner. Everything below 18 is even bigger, so column 3 is out. |
| 2 | 0 | 2 | 11 | 11 < 13, so row++ | Everything to the left of 11 in row 0 is smaller, so row 0 is out. |
| 3 | 1 | 2 | 14 | 14 > 13, so col-- | Column 2 from here down holds 14, 19, and 23, all too big. |
| 4 | 1 | 1 | 9 | 9 < 13, so row++ | Row 1 from here left holds 9 and 4, both too small. |
| 5 | 2 | 1 | 12 | 12 < 13, so row++ | 12 is close, but too small, and so is 7 to its left. |
| 6 | 3 | 1 | 16 | 16 > 13, so col-- | This is the last row. 16 is too big, so column 1 is out. |
| 7 | 3 | 0 | 10 | 10 < 13, so row++ | 10 is too small and nothing is to its left, so the last row is out. |
| 8 | 4 | 0 | - | row === grid.length: stop | The walk stepped off the bottom. Every row has been ruled out. |
It returns [-1, -1] after 7 checks out of 16 cells. The walk can never take more than 4 + 4 - 1 = 7 checks on this grid, so this was the worst case.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Staircase search in a sorted grid | O(rows + cols) | O(1) | Rows and columns are both sorted, and the grid's sides are not wildly different in length. |
| Binary search each row | O(rows × log cols) | O(1) | One side is much shorter than the other, like 5 rows by 100,000 columns, or only the rows are sorted. |
| Check every cell | O(rows × cols) | O(1) | The grid is tiny or isn't sorted at all. |
Extra memory: O(1): just row, col, and value.
How the steps grow
- Staircase search in a sorted grid
O(rows + cols) - Binary search each row
O(rows × log cols) - Check every cell
O(rows × cols)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Staircase search in a sorted grid | 20 | 2,000 | 2 million |
| Binary search each row | 33 | 9,966 | 20 million |
| Check every cell | 100 | 1 million | 1 trillion |
Inputs that need care
5 tricky inputs
- An empty grid:
grid = [] - The first line returns
[-1, -1]before readinggrid[0].length, which would throw an error. - Rows with no cells:
grid = [[]] colstarts at-1, socol >= 0is false and the loop never runs. It returns[-1, -1]without an error.- A single row:
[[3, 8, 15]], target8 - The walk steps left from
15to8and returns[0, 1]. On one row this is a scan from the right,O(cols), where plain binary search would beO(log cols). - Duplicates:
[[1, 5], [5, 9]], target5 - It returns the first
5the walk meets, here[0, 1]. Equal values don't break the walk, because the rules only need "at least" and "at most" order. - A very wide grid: 3 rows and 100,000 columns
- The walk can take about 100,000 steps. Binary searching each of the 3 rows takes about
3 × 17 = 51checks, which is much faster when one side is far longer than the other.
Variations and follow-ups
Twists interviewers add
Start at the bottom-left
The bottom-left cell is the smallest in its row and the largest in its column, so it works too: step up when too big and right when too small. Both corners give the same speed. The top-left and bottom-right corners don't work.
Count cells at most a limit
Walk from the bottom-left. When grid[row][col] <= limit, the whole column above is also <= limit, so add row + 1 and step right; otherwise step up. This counts in O(rows + cols). Binary searching a value with this count finds the k-th smallest cell in O((rows + cols) log R), where R is the value range.
A grid that is one sorted list
If each row starts after the previous row ends, the grid is one sorted list folded into rows. Binary search a position i from 0 to rows × cols - 1 and read grid[Math.floor(i / cols)][i % cols], for O(log(rows × cols)).
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "each row is sorted left to right and each column is sorted top to bottom". If it says instead that "the first item of each row is bigger than the last item of the row before", the grid is one sorted list: use plain binary search.
- Explain why the corner works: "the top-right cell is the biggest in its row and the smallest in its column, so one comparison always rules out a whole row or column". Then say why the top-left corner fails.
- Test by hand: an empty grid, a one-row grid, a target in the bottom-left corner (the longest path), and a missing target.
- A common follow-up is "find the k-th smallest value". Answer: binary search on the value from
grid[0][0]to the bottom-right cell, and for each guess count the cells<= midwith a staircase walk from the bottom-left.
Where frontend code uses it
The same idea in real UI code
- A shipping or pricing table where the price rises with weight (rows) and distance (columns): checking if a given price exists, or counting options under a budget, is this walk.
- Counting cells under a limit in a sorted grid is the inner step when you binary search for a percentile in such a table.
- The same "step one of two pointers" idea appears when you merge or compare two sorted lists, such as matching sorted IDs from two API responses.