
Description
The problem is to search for a target value in a 2D matrix where each row is sorted in ascending order, and each column is sorted in ascending order. The task is to determine whether the target value exists within the matrix.
Intuition
Given that the matrix is sorted both row-wise and column-wise, we can leverage this property to eliminate rows or columns efficiently, thereby narrowing down the search space. Starting from the top-right corner allows us to make decisions about whether to move left or down based on the comparison between the current element and the target.
Approach
- Initialization: Start from the top-right corner of the matrix.
- Search:
- Compare the current element with the target.
- If the current element is equal to the target, return
True
. - If the current element is greater than the target, move left to reduce the value. - If the current element is less than the target, move down to increase the value. - Termination: If we move out of the matrix bounds, return
False
as the target does not exist in the matrix.
Complexity
Time Complexity:
The time complexity is O(m + n), where m
is the number of rows and n
is the number of columns. In the worst case, we might traverse one row and one column completely.
Space Complexity:
The space complexity is O(1) since we are only using a constant amount of extra space.
Code
C++
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
int row = 0;
int col = matrix[0].size() - 1;
while (row < matrix.size() && col >= 0) {
if (matrix[row][col] == target) {
return true;
}
if (matrix[row][col] < target) {
row++;
} else {
col--;
}
}
return false;
}
};
Python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row = 0
col = len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
if matrix[row][col] < target:
row += 1
else:
col -= 1
return False
Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) {
return true;
}
if (matrix[row][col] < target) {
row++;
} else {
col--;
}
}
return false;
}
}
JavaScript
var searchMatrix = function(matrix, target) {
let row = 0;
let col = matrix[0].length;
while(row < matrix.length && col >= 0){
if(matrix[row][col] === target){
return true
}
if(matrix[row][col] < target){
row++
} else{
col--
}
}
return false;
};