Search a 2D Matrix II

Medium

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 order from left to right.
Integers in each column are sorted in ascending order from top to bottom.

Return true if the target exists in the matrix, otherwise return false.

Example 1

Input

m = 5
n = 5
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

Explanation

The target 5 exists in the matrix.

Example 2

Input

m = 5
n = 5
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

Explanation

The target 20 does not exist in the matrix.

Constraints

m == matrix.length

n == matrix[i].length

1 <= m

n <= 300

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

All rows are sorted in ascending order.

All columns are sorted in ascending order.

-10^9 <= target <= 10^9

Hints:

Hint 1

Start from the top-right corner of the matrix.

Hint 2

At position (row, col):

If matrix[row][col] == target, return true.
If matrix[row][col] > target, move left.
If matrix[row][col] < target, move down.

Auto

Loading editor...

Input

Expected Output