Dare2Solve
Given a m x n
matrix and a target number, the task is to determine if the target exists in the matrix. The matrix has the following properties:
To efficiently find the target in the matrix, we can leverage its sorted properties. By performing binary searches, we can narrow down the potential rows and columns where the target might be located.
First Binary Search:
left
and right
to the first and last rows, respectively.mid
) and check if the target lies between the first and last elements of this row.right
pointer to mid - 1
.left
pointer to mid + 1
.Second Binary Search:
left
and right
pointers to the start and end of the columns of the identified row.mid
) and compare its value with the target.mid
equals the target, return True
.mid
, adjust the right
pointer to mid - 1
.mid
, adjust the left
pointer to mid + 1
.Return Result:
False
.O(log(m) + log(n)) = O(log(mn)), where m
is the number of rows and n
is the number of columns. This is because we perform binary search twice, first on the rows and then on the columns.
O(1), as we use a constant amount of extra space.
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int left = 0;
int right = matrix.size() - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid][0] <= target && matrix[mid][matrix[mid].size() - 1] >= target) {
left = 0;
right = matrix[mid].size() - 1;
index = mid;
break;
}
if (matrix[mid][0] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (index == -1) {
return false;
}
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[index][mid] == target) {
return true;
}
if (matrix[index][mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
};
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
left = 0
right = len(matrix) - 1
index = -1
# First binary search to find the correct row
while left <= right:
mid = left + (right - left) // 2
if matrix[mid][0] <= target <= matrix[mid][-1]:
left = 0
right = len(matrix[mid]) - 1
index = mid
break
elif matrix[mid][0] < target:
left = mid + 1
else:
right = mid - 1
if index == -1:
return False
while left <= right:
mid = left + (right - left) // 2
if matrix[index][mid] == target:
return True
elif matrix[index][mid] < target:
left = mid + 1
else:
right = mid - 1
return False
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int left = 0;
int right = matrix.length - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid][0] <= target && matrix[mid][matrix[mid].length - 1] >= target) {
left = 0;
right = matrix[mid].length - 1;
index = mid;
break;
}
if (matrix[mid][0] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// If no valid row is found, return false
if (index == -1) {
return false;
}
// Second binary search within the identified row
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[index][mid] == target) {
return true;
}
if (matrix[index][mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
var searchMatrix = function(matrix, target) {
let left = 0;
let right = matrix.length-1;
let index = -1;
while( left <= right ){
let mid = Math.floor( ( left + right ) / 2 );
if( matrix[mid][0] <= target && matrix[mid][matrix[mid].length-1] >= target ){
left = 0;
right = matrix[mid].length-1;
index = mid
break
}
if( matrix[mid][0] < target ){
left = mid+1
}else{
right = mid-1
}
}
while(left <= right ){
let mid = Math.floor(( left + right ) / 2 );
if( matrix[index][mid] == target ){
return true
}
if( matrix[index][mid] < target ){
left = mid+1
}else{
right = mid-1
}
}
return false
};