Search a 2D Matrix
Search a matrix whose rows are increasing and whose first value in each row exceeds the last value of the preceding row.
Work through the cases
3 examplesInput notation
Target on line 1, followed by space-separated matrix rows.Expected result
true or false.Case 1
Input
7 1 3 5 7 9 11
Expected output
true
Case 2
Input
4 1 3 5 7
Expected output
false
Case 3
Input
-3 -3
Expected output
true
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A full scan is O(mn). m,n ≤ 100 would pass, but the problem asks for O(log(mn)). Two dimensions hide a single binary search. Each row increases, and the last of row i is less than the first of row i+1, so concatenating rows is a sorted array of length mn. Logical index mid maps to matrix[\lfloor mid/n\rfloor][mid \bmod n], so we binary-search [0,mn-1] without materializing the flatten.
We can logically unfold the two-dimensional matrix and then perform binary search.
The time complexity is O(log(m × n)), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left < right) {
int mid = (left + right) >> 1;
int x = mid / n, y = mid % n;
if (matrix[x][y] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return matrix[left / n][left % n] == target;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.