Each row of an m × n matrix is sorted, and each row's first value is greater than the previous row's last value. Return whether the target is in the matrix, in O(log(m × n)).
Before you code
Read row by row, the matrix is one sorted list of m × n numbers. You don't need to copy it: convert each flat index to a row and column.
Hints
- Binary search flat indexes
[0, m * n). - Flat index
kismatrix[k // n][k % n]. - Alternative: binary search the first column to pick the row, then search that row. Same complexity, more boundaries to get right.
Production & complexity notes
When solving Search a 2D matrix 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
Combining index arithmetic with binary search, from Rotated and two-dimensional data.