74. Search a 2D Matrix
You are given an m × n integer matrix with a strict layered order:
- every row is sorted in ascending order, and
- the first value of each row is strictly greater than the last value of the row above it.
Read row by row, the whole matrix is one sorted list that just happens to be stored in m pieces.
Given an integer target, return true if it appears anywhere in the matrix and false otherwise. Scanning every cell works, but the ordering is begging for better — the goal is O(log(m·n)) time.
Example 1:
Input: matrix = [[1, 4, 7, 10], [12, 15, 18, 21], [23, 26, 29, 32]], target = 15
Output: true
Explanation: 15 sits at row 1, column 1, so the answer is true.
Example 2:
Input: matrix = [[1, 4, 7, 10], [12, 15, 18, 21], [23, 26, 29, 32]], target = 16
Output: false
Explanation: 16 would have to live between 15 and 18 in the middle row, but nothing is stored there — it is absent, so the answer is false.
Constraints:
- 1 ≤ m, n ≤ 100
- -10⁴ ≤ matrix[i][j], target ≤ 10⁴
- Each row is sorted ascending, and matrix[i][0] > matrix[i-1][n-1] for every i ≥ 1
Hints:
Because each row starts past where the previous one ends, concatenating the rows produces a single fully sorted array of m·n values. You never need to build it — you only need to be able to read a value at any virtual position.
Binary search over the virtual indices 0 … m·n − 1. The value at virtual index k is matrix[k / n][k % n] (integer division and remainder). Compare it with the target and halve the range as usual — that is one binary search, O(log(m·n)).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[1, 4, 7, 10], [12, 15, 18, 21], [23, 26, 29, 32]], target = 15
Expected output: true