# Search a row and column sorted matrix

HardGiven a

`matrix`

of numbers of size `m x n`

, and a `target`

number, write a function that determines if the `target`

number exists in the `matrix`

.Every row and every column is

*sorted*in ascending order in the given`matrix`

.For example, if your function recieves the following 3x3 matrix and target number:

matrix = [[1, 3, 8, 10],[2, 5, 9, 11],[3, 6, 10, 15],[5, 7, 12, 18],]target = 6

Your function should return

`True`

.Given the same matrix, if the

`target`

is `4`

, your function should return `False`

.Note how in

`matrix`

, every row and column is sorted, but is not necessarily greater than the previous row or column.## Try it

Before you look at the solution, try to code it yourself.

## Solution

### Time and Space Complexity

On each iteration we either remove an entire row or an entire column.

Therefore, our time complexity is

`O(m + n)`

.There is no additional space required. So the space complexity constant

`O(1)`

.## 5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

- 1.Merge intervalsMedium
- 2.Kth largest in arrayMedium
- 3.Intersection of ArraysMedium
- 4.Search sorted matrixHard
- 5.Search row & col sorted matrixHard