visual walkthrough
Search a 2D Matrix
Treat a matrix as a flattened sorted array.
The idea
Each row is sorted and each row starts after the previous one ends, so reading row by row gives one long sorted list.
Binary search that list without building it: position p lives at row p / C, column p mod C.
Complexity
| approach | time | space |
|---|---|---|
| Check every cell | O(R · C) | O(1) |
| Binary search as one list | O(log(R · C)) | O(1) |