February LeetCoding Challenge 2021
Day 23
Search a 2D Matrix II
PROBLEM STATEMENT:
Write an efficient algorithm that searches for a
Example 1
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.
Example 2![]()
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true
Constraints:![]()
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Explanation
Start with the top right corner. If the value if greater than the target value move left else move down.
ALGORITHM:
- Start at top right corner.
- If the current value is greater than the target value move left.
- Else move down.
- Repeat uniti you go out of bounds.
- Time complexity : O(n+m)
- Space complexity : O(1)
code
C++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int row = 0;
int col = n-1;
while(col>=0 && row<m){
if(matrix[row][col] == target) return true;
if(matrix[row][col] > target) --col;
else ++row;
}
return false;
}
};
PYTHON
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
row = 0
col = n-1
while(col>=0 and row<m):
if(matrix[row][col] == target):
return True
if(matrix[row][col] > target):
col -= 1
else:
row += 1
return False