Given an integer matrix matrix with m rows and n columns, determine whether the integer target exists in matrix.

The matrix has the following ordering properties:
Each row of matrix is sorted in ascending order from left to right.
Each column of matrix is sorted in ascending order from top to bottom.

Return true if target is present in matrix, otherwise return false.

Constraints:

• m == matrix.length

• n == matrix[i].length

• $1 \leq `n`, `m` \leq 300$

• $-10^9 \leq `matrix[i][j]` \leq 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 \leq `target` \leq 10^9$

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

Explanation:
Start from the top-right corner (15). Since 15 > 5, move left to 11, then 7, then 4. Now 4 < 5, so move down to 5, which matches the target.

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

Explanation:
Using the same top-right search: 15 < 20 (go down), 19 < 20 (down), 22 > 20 (left), 16 < 20 (down), 17 < 20 (down), 26 > 20 (left), 23 > 20 (left), 21 > 20 (left), 18 < 20 (down) and you run out of rows. Since the search space is exhausted, 20 is not in the matrix.

Input:

• matrix = [[-5]]

• target = -5

Output:

• true

Explanation:
Single-cell matrix: the only value equals the target.

Input:

• matrix = [[1,2,3,4],[5,6,7,8]]

• target = 9

Output:

• false

Explanation:
From top-right (4), move down to 8 because 4 < 9. Since 8 < 9 and there are no more rows below, the target cannot be present.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.