A sensor log is stored as an m x n grid table in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom. Note that the rows do not continue one another: the first value of a row may be smaller than the last value of the row above.
Return True if target appears anywhere in the table and False otherwise.
Examples
Input: table = [[2, 5, 8], [3, 6, 11], [7, 9, 14]], target = 6
Output: True
Input: table = [[2, 5, 8], [3, 6, 11], [7, 9, 14]], target = 10
Output: False
Explanation: 10 lies between 9 and 11 but is not stored.
Constraints
1 <= m, n <= 500- Target: O(m + n) time, O(1) extra space. Note that O(m * log n) is easy but not optimal.
Goals
- Exploit sortedness along both rows and columns at the same time
- Eliminate a whole row or a whole column with each comparison
- Reach O(m + n) time without any extra space