visual walkthrough
Search a 2D Matrix II
Start at a corner and eliminate a row or column per step.
The idea
Rows and columns are sorted, but the matrix isn't one sorted list, so plain binary search doesn't apply.
The top-right corner is special: it's the largest in its row and the smallest in its column. Comparing it with the target always rules out a whole row or column.
Complexity
| approach | time | space |
|---|---|---|
| Check every cell | O(R · C) | O(1) |
| Staircase from the top-right | O(R + C) | O(1) |