Search a Row- and Column-Sorted Matrix

Each row of matrix is sorted in increasing order, and each column is sorted in increasing order too (but a row does not have to start after the previous one ends). Return True if target is in the matrix.

Examples

Example 1

Input:

search_matrix_ii([[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]], 5)

Output:

True

Example 2

Input:

search_matrix_ii([[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]], 15)

Output:

False

Constraints

• 0 <= rows, cols, and rows * cols <= 2 * 10**5
• Every row and every column is sorted in increasing order.
• -10**9 <= matrix[i][j], target <= 10**9
• The big tests count how many cells you read.