Given an m x n integer matrix, where:

Each row is sorted in non-decreasing order from left to right.

Each column is sorted in non-decreasing order from top to bottom.

Write an efficient algorithm to determine whether a given integer target exists in the matrix. Return true if target is found and false otherwise.

Follow-up: Can you solve this problem in O(m + n) time complexity?

Example 1:

Input: matrix = [
  [2, 6, 10, 14, 18],
  [5, 9, 13, 17, 22],
  [8, 12, 16, 21, 26],
  [11, 15, 20, 24, 30],
  [14, 19, 25, 28, 35]
]
target = 17
Output: true
Explanation: The value 17 exists in the matrix at row 1, column 3, so the function returns true.

Example 2:

Input: matrix = [
  [2, 6, 10, 14, 18],
  [5, 9, 13, 17, 22],
  [8, 12, 16, 21, 26],
  [11, 15, 20, 24, 30],
  [14, 19, 25, 28, 35]
]
target = 23
Output: false
Explanation: The value 23 does not exist anywhere in the matrix, so the function returns false.

Example 3:

Input: matrix = [
  [-5],
  [-2],
  [0],
  [3],
  [9]
]
target = 3
Output: true
Explanation: The target 3 exists in the only column of the matrix, so the function returns true.

Constraints

m == matrix.length

n == matrix[i].length for every valid row i

1 <= m, n <= 300

−10⁹ <= matrix[i][j] <= 10⁹

All the integers in each row are sorted in ascending order.

All the integers in each column are sorted in ascending order.

−10⁹ <= target <= 10⁹

77. Search in Sorted Matrix