###### Search a 2D Matrix II | February Leetcoding challenge 2021 | Day 23
Manas Sinha
Developer | Designer

## Search a 2D Matrix II

`PROBLEM  STATEMENT:`
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.
Example 1
```

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
```
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 = 20
Output: false
```
Constraints:
• `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)

## 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
``````