Sponsored
Sponsored
The matrix can be viewed as a single sorted list. Hence, we can perform a binary search on the entire matrix by treating it as a 1D array. Suppose we have a matrix of size m x n, any element in the matrix can be accessed using a single index calculated as follows:
Element at index k can be accessed using matrix[k / n][k % n], where / and % represent integer division and modulus operations, respectively.
This approach ensures that the solution operates in O(log(m * n)) time complexity as required.
Time complexity: O(log(m * n))
Space complexity: O(1)
1class Solution {
2 public boolean searchMatrix(int[][] matrix, int target) {
3 int m = matrix.length;
4 int n = matrix[0].length;
5 int left = 0, right = m * n - 1;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 int midVal = matrix[mid / n][mid % n];
9 if (midVal == target) return true;
10 else if (midVal < target) left = mid + 1;
11 else right = mid - 1;
12 }
13 return false;
14 }
15}The key is to use integer division and modulus operations to map a 1D index to 2D matrix indices. Java's solution handles this efficiently within the same time complexity.
The problem also allows for a two-step binary search owing to the special properties of the matrix. First, we identify the row which potentially contains the target by performing binary search on first elements of each row. Then, we conduct a binary search in that specific row.
Although not strictly O(log(m * n)), this approach exploits the matrix's properties in an efficient manner for similar effective results.
Time complexity: O(log(m) + log(n))
Space complexity: O(1)
1 public bool SearchMatrix(int[][] matrix, int target) {
int m = matrix.Length;
int n = matrix[0].Length;
int top = 0, bottom = m - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
if (matrix[mid][0] <= target && target <= matrix[mid][n - 1]) {
top = mid;
break;
}
if (matrix[mid][0] < target) {
top = mid + 1;
} else {
bottom = mid - 1;
}
}
if (top > bottom) return false;
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[top][mid] == target) return true;
else if (matrix[top][mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
}The C# solution adopts a combined row and column binary search approach, increasing efficiency by minimizing column search space post row identification.