In an m × n matrix, every row is sorted left to right and every column top to bottom. Return whether the target is present.
Before you code
The rows don't continue each other, so the matrix is not one sorted sequence and flat binary search is wrong. Find a starting cell from which every comparison rules out a whole row or column.
Hints
- Start at the top-right corner: the largest value in its row and the smallest in its column.
- If the target is smaller, the whole current column is too big: move left. If larger, the whole row is too small: move down.
- Stop when found or when you leave the matrix. At most m + n steps.
Production & complexity notes
When solving Search a 2D matrix II on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Rotated and two-dimensional data to reinforce the underlying pattern.
What it practices
Ruling out regions with each comparison, from Rotated and two-dimensional data.