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

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

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`

Intuition

Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively), we can prune `O(m)` or `O(n)` elements when looking at any particular value.

Algorithm

First, we initialize a `(row,col) `pointer to the bottom-left of the matrix. Then, until we find `target` and return `true` (or the pointer points to a `(row,col)` that lies outside of the dimensions of the matrix), we do the following: if the currently-pointed-to value is larger than `target` we can move one row “up”. Otherwise, if the currently-pointed-to value is smaller than `target`, we can move one column “right”. It is not too tricky to see why doing this will never prune the correct answer; because the rows are sorted from left-to-right, we know that every value to the right of the current value is larger. Therefore, if the current value is already larger than `target`, we know that every value to its right will also be too large. A very similar argument can be made for the columns, so this manner of search will always find `target` in the matrix (if it is present).

```class Solution {
public boolean searchMatrix(int[][] matrix, int target) {

if(matrix == null || matrix.length == 0){
return false;
}
int m = matrix.length;
int n = matrix.length;
int i = (m - 1);
int j = 0;
while( i >= 0 && j < n){
int cur = matrix[i][j];
if(cur == target){
return true;
}else if(target > cur){
j++;
}else{
i--;
}
}
return false;
}
}
```

Complexity Analysis

• Time Complexity : `O(n+m)`
• Space Complexity : `O(1)`

Categories: 2D Array, Array