# Leetcode 240. Search a 2D Matrix II

# Problem Statement

Write an efficient algorithm that searches for a value `target`

in an `m x n`

integer matrix `matrix`

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

# Test Cases

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

`-10^9 <= matrix[i][j] <= 10^9`

- All the integers in each row are
**sorted**in ascending order. - All the integers in each column are
**sorted**in ascending order. `-10^9 <= target <= 10^9`

# Approach

So in this problem we have to look for a number say **target** inside the given matrix. We actually do a normal **row * col **traversal inside the matrix and look for the **target **value. But this is the method if no other speciality about the matrix is given to us.

In the question, we are given that the numbers in each row is sorted from left to right and numbers in each column is sorted from top to bottom in ascending order. So how this helps us.

Suppose we keep our **rowPointer to the first row** and the **colPointer to the last column **and do a loop until we reach the last row and the first column.

Inside the loop, just check for the target we are looking for, if we find it then we are good and return **true. **Else we are left with 2 possibilities.

- Either the current number can be greater than the target. This time we just move the column pointer to the left as the number cannot be present in that entire column as we know the entire column is sorted.
- Or the current number can be lesser than the target. This time we just move the row pointer down as the number cannot be present in that entire column as we know the entire row is also sorted.

**Algorithm**

- Use 2 pointer says
**rowP = 0 and colP = col — 1.** - Run until
**rowP < row && colP ≥ 0.** - Check for the target inside the matrix. ie
`matrix[rowP][colP] == target`

.**Return true**here. - Check whether
`matrix[rowP][colP] > target`

, do**colP -= 1.** - Check whether
`matrix[rowP]colP] < target`

, do**rowP += 1.** - If we get out of the loop, then the target is not present inside the matrix else we should have caught it from inside the loop. Return false.

# Time and Space Complexity

We are moving row and col one at a time. So our time complexity will be **O(row + col).**

No extra space is being used here. So our space complexity will be **O(1).**