This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Write an efficient algorithm that searches for a value in an *m* x *n* 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.

For example,

Consider the following 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] ]

Given **target** = `5`

, return `true`

.

Given **target** = `20`

, return `false`

.

b'

\n#### Approach #1 Brute Force [Accepted]

\n

\n#### Approach #2 Search Space Reduction [Accepted]

\n

\n#### Footnotes

\n

'
\n\n

\n**Intuition**

As a baseline, we can search the 2D array the same way we might search an\nunsorted 1D array -- by examining each element.

\n**Algorithm**

The algorithm doesn\'t really do anything more clever than what is explained\nby the intuition; we loop over the array, checking each element in turn. If\nwe find it, we return `true`

. Otherwise, if we reach the end of the nested\n`for`

loop without returning, we return `false`

. The algorithm must return\nthe correct answer in all cases because we exhaust the entire search space.

**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nBecase we perform a constant time operation for each element of an\n element matrix, the overall time complexity is equal to the\nsize of the matrix.

\n \n - \n
Space complexity : \n

\nThe brute force approach does not allocate more additional space than a\nhandful of pointers, so the memory footprint is constant.

\n \n

\n

**Intuition**

Because the rows and columns of the matrix are sorted (from left-to-right and\ntop-to-bottom, respectively), we can prune one row or one\n column when looking at any particular value.

\n**Algorithm**

First, we initialize a pointer to the bottom-left of the\nmatrix.^{1} Then, until we find `target`

and return `true`

(or the pointer\npoints to a that lies outside of the dimensions of the\nmatrix), we do the following: if the currently-pointed-to value is larger\nthan `target`

we can move one row "up". Otherwise, if the\ncurrently-pointed-to value is smaller than `target`

, we can move one column\n"right". It is not too tricky to see why doing this will never prune the\ncorrect answer; because the rows are sorted from left-to-right, we know that\nevery value to the right of the current value is larger. Therefore, if the\ncurrent value is already larger than `target`

, we know that every value to\nits right will also be too large. A very similar argument can be made for the\ncolumns, so this manner of search will always find `target`

in the matrix (if\nit is present).

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

\n!?!../Documents/240_Search_a_2D_Matrix_II.json:1280,720!?!

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nThe key to the time complexity analysis is noticing that, on every\niteration (during which we do not return

\n`true`

) either`row`

or`col`

is\nis decremented/incremented exactly once. Because`row`

can only be\ndecremented times and`col`

can only be incremented times\nbefore causing the`while`

loop to terminate, the loop cannot run for\nmore than iterations. Because all other work is constant, the\noverall time complexity is linear in the sum of the dimensions of the\nmatrix. \n - \n
Space complexity : \n

\nBecause this approach only manipulates a few pointers, its memory\nfootprint is constant.

\n \n

\n

Analysis and solutions written by: @emptyset

\n\n

\n

\n\n

- \n
- \n
This would work equally well with a pointer initialized to the\ntop-right. Neither of the other two corners would work, as pruning a\nrow/column might prevent us from achieving the correct answer.\xc2\xa0\xe2\x86\xa9

\n \n