Dare2Solve
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.
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.
True
.False
as the target does not exist in the matrix.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.
The space complexity is O(1) since we are only using a constant amount of extra space.
class Solution {
public:
bool searchMatrix(vector<vector<int>>& 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;
}
};
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
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;
}
}
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;
};