Search a 2D Matrix II
Medium · matrix
A seating chart is a grid of integers matrix with m rows and n columns. Inside every row the numbers get strictly larger from left to right, and inside every column they get strictly larger from top to bottom. Different rows and columns are not otherwise related, so the same number can appear in several places.
Given an integer target, return true if it appears anywhere in the grid, and false otherwise.
Examples
Example 1
Input: matrix = [[1, 3, 5, 9], [2, 4, 8, 10], [6, 7, 11, 14], [12, 13, 15, 18]], target = 8
Output: true
8 is in the second row, third column.
Example 2
Input: matrix = [[1, 3, 5, 9], [2, 4, 8, 10], [6, 7, 11, 14], [12, 13, 15, 18]], target = 16
Output: false
16 falls between neighbours in every row and column that could hold it, but it is not in the grid.
Example 3
Input: matrix = [[-4, 0, 7]], target = 0
Output: true
Constraints
- 1 <= m, n <= 300
- -10^9 <= matrix[i][j], target <= 10^9
- Each row is strictly increasing and each column is strictly increasing.