Search a 2D Matrix II - Medium - L
Published:
Question
- https://leetcode.com/problems/search-a-2d-matrix-ii/
Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Approach
- Start from bottom left and then move one row up if the target is lesser and go to the right.
Solution
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n=matrix.size();
if(n==0){
return false;
}
int m=matrix[0].size();
if(m==0){
return false;
}
int i=0;
int j=m-1;
while(i<n && j>=0){
if(matrix[i][j]==target){
return true;
} else if(matrix[i][j]>target){
j--;
} else{
i++;
}
}
return false;
}
};