# Search a 2D Matrix

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.

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

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

## Approach : Search Space Reduction

**Intuition**

Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively).

**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).

Check out some sample runs of the algorithm in the animation below:

**Implementation**:

**Complexity Analysis**

- Time complexity : O(
*n*+*m*) - The key to the time complexity analysis is noticing that, on every iteration (during which we do not return
`true`

) either`row`

or`col`

is decremented/incremented exactly once. Because`row`

can only be decremented*m*times and`col`

can only be incremented*n*times before causing the`while`

loop to terminate, the loop cannot run for more than*n*+*m*iterations. Because all other work is constant, the overall time complexity is linear in the sum of the dimensions of the matrix. - Space complexity : O(1).