Why it works
- Each row is sorted and starts above the end of the row before it, so the rows read one after another form one sorted list of rows · cols numbers.
- Binary search runs over that list’s indices without building it: index k is row floor(k / cols), column k mod cols. Here mid = 8 lands on 23, the first number of row 2.
- One search over all cells takes about log(rows · cols) steps, the same as finding the row first and then searching inside it.
Complexity
Time O(log(m · n)) for m rows and n columns: every step halves the range of cells. Memory O(1): the matrix is never copied into a list.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗