The problem
Search for a target in a matrix where every row is sorted left-to-right and every column top-to-bottom. Rows are NOT globally sorted.
Stuck? Reveal hints one at a time
How to approach it
- 1Start at row 0, last column.
- 2Current value equals the target → found.
- 3Current value > target → the whole column below is even larger: move left.
- 4Current value < target → the whole row to the left is even smaller: move down.
- 5Falling off the matrix means the target is absent.
Key insight
The top-right corner is the unique cell where the two sort orders point in OPPOSITE directions — every comparison eliminates a full row or column.
The solution
Watch out for
- The bottom-left corner works symmetrically; the other two corners do not.
- Binary-searching each row is O(rows · log cols) — acceptable but strictly worse.