🎨Now live: Try our Free AI Image Generation Feature

Description
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:
- Integers in each row are sorted in ascending order from left to right.
- Integers in each column are sorted in ascending order from top to bottom.
Intuition
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.
Approach
- First Binary Search:
- Perform a binary search on the first column of the matrix to identify the row in which the target could potentially exist.
- Initialize two pointers
left
andright
to the first and last rows, respectively. - Calculate the middle row (mid
) and check if the target lies between the first and last elements of this row. - If it does, narrow down to this row for further searching. - If the target is less than the first element of the middle row, adjust theright
pointer tomid - 1
. - If the target is greater than the last element of the middle row, adjust theleft
pointer tomid + 1
. - Second Binary Search:
- Once the correct row is identified, perform a binary search within this row.
- Adjust
left
andright
pointers to the start and end of the columns of the identified row. - Calculate the middle column (mid
) and compare its value with the target. - If the value atmid
equals the target, returnTrue
. - If the target is less than the value atmid
, adjust theright
pointer tomid - 1
. - If the target is greater than the value atmid
, adjust theleft
pointer tomid + 1
. - Return Result:
- If the target is not found within the identified row, return
False
.
Complexity
Time Complexity:
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.
Space Complexity:
O(1), as we use a constant amount of extra space.
Code
C++
class Solution {
public:
bool searchMatrix(vector>& 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;
}
};
Python
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
Java
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;
}
}
JavaScript
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
};