Sorted Matrix Search
Signal words
If the prompt uses any of these, this pattern should come to mind first.
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Are both rows and columns sorted ascending?
- Is there a corner where one direction means “smaller” and the other means “larger”?
- Can you eliminate a whole row or column with a single comparison?
Classic problem
Search a 2D Matrix II (LeetCode 240) — each row and column is sorted ascending.
Return whether target exists. Start at the top-right corner: it’s the largest in
its row and the smallest in its column, so every comparison rules out a full line.
Input: matrix = [[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]], target = 13
Output: true — starting top-right at 15, step left to 11, step down twice to 13.
Each step discards one row or column, so the walk visits at most m + n cells —
O(m + n) time, O(1) space.
Common pitfalls
Starting at the top-left (or bottom-right) corner — both neighbors move the same direction, so you can’t eliminate a line.
Forgetting the empty-matrix guard;
matrix[0]throws on a zero-row input.
Reaching for binary search per row (
O(m log n)) when the staircase is simpler and faster.