Staircase search in a sorted matrix

44 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Here is a 5 × 5 grid in which every row increases left to right and every column increases top to bottom. Is 5 in it?

Scanning all 25 cells works but ignores the ordering. Binary searching each row is better, 5 rows × about 3 steps, but still touches every row. The ordering is stronger than that: it holds in two directions at once, and there is a corner from which each step throws away a whole row or column.

Build the structure, one piece at a time

Stand on the top-right cell, 15. Look at what you know about it. Everything to its left in that row is smaller than 15. Everything below it in that column is larger than 15. So 15 is the largest in its row and the smallest in its column. That gives a rule with only two moves:

• If the cell is larger than the target, the whole column below it is also larger, so the target cannot be in this column. Step left.
• If the cell is smaller than the target, the whole row to its left is also smaller, so the target cannot be in this row. Step down.

Follow it for the target 5. The region that might still hold the target shrinks after each step:

1. At 15 (row 0, column 4): 15 > 5, drop column 4, step left to 11.
2. At 11: 11 > 5, drop column 3, step left to 7.
3. At 7: 7 > 5, drop column 2, step left to 4.
4. At 4: 4 < 5, drop row 0, step down to 5.
5. At 5: equal, found at row 1, column 1.

The path is a staircase from the top-right corner towards the bottom-left, which gives the pattern its name. Starting from the bottom-left corner works equally well, with the moves mirrored; the top-left and bottom-right corners do not work, because from them both moves go in the same direction (both bigger, or both smaller) and nothing can be discarded.

Why it is correct

The invariant is that the target, if present, lies in the rectangle from the current cell's row downwards and from its column leftwards. At the top-right corner that rectangle is the whole grid, so the invariant starts true. Suppose the current cell c is larger than the target t. Every cell below c in its column is at least c > t, so none of them is the target, and removing that column keeps the invariant. Suppose instead c < t. Every cell to the left of c in its row is at most c < t, so removing that row keeps the invariant. If the rectangle becomes empty the target is absent; if the current cell equals the target we are done.

Why it is fast

Every step removes either one row or one column, and there are only m rows and n columns, so the number of steps is at most m + n: at most 10 for the 5 × 5 grid, against 25 for a scan. The time is O(m + n) with O(1) extra memory. Binary searching each row costs O(m log n), which is worse whenever m is large.

steps ≤ (number of rows dropped) + (number of columns dropped) ≤ m + n

How to recognise it in an interview

Cues: "each row is sorted and each column is sorted", "count the negatives", "how many cells are at most x". The second and third cues matter because the same walk counts cells: when you step down after a cell smaller than x, every cell to the left in that row is also at most x, so you add the column index plus one to a counter. Say: "the grid is sorted in two directions, so from the top-right corner each comparison discards a whole row or column".

Search a 2D Matrix II is the walk-through. Count Negative Numbers in a Sorted Matrix is the counting form. Kth Smallest Element in a Sorted Matrix combines the counter with a binary search over values: guess a value, count cells at most that value with the staircase in O(m + n), and tighten the guess.

02The idea in one line

Start at the top-right: go left if too big, down if too small.

Reach for it when: Search a 2D matrix II, count negatives, kth smallest in a sorted matrix (counting).

Cost: O(m + n) time.

03The walk-through, step by step

The video works one example: Search 5 in a 5×5 sorted matrix. These are its captions in order, so you can follow without the video or check a step you missed.

1. Start at the top-right: left is smaller, down is bigger
2. 15 > 5: the column below is all bigger, go left
3. Candidates shrink to the blue region; now at 11
4. 11 > 5: the column below is all bigger, go left
5. Candidates shrink to the blue region; now at 7
6. 7 > 5: the column below is all bigger, go left
7. Candidates shrink to the blue region; now at 4
8. 4 < 5: the row to the left is all smaller, go down
9. Candidates shrink to the blue region; now at 5
10. 5 == 5: found at (1,1)
11. Each step discards a full row or column: at most m + n moves
12. O(m + n) time, O(1) space

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Matrix: Matrix traversal and rotation.