233. Staircase Search
A library shelves its catalogue numbers in a rectangular grid grid. The shelving rules are strict: in every row the numbers increase from left to right, and in every column the numbers increase from top to bottom. Given a catalogue number target, decide whether it is on the shelves.
Return true if target appears somewhere in the grid and false otherwise. The grid can have millions of cells, so checking every one of them is too slow. Use the ordering of rows and columns to discard a whole row or a whole column at every step.
Example 1
- Input:
- grid = [[2,5,9],[4,7,12],[6,10,15]], target = 10
- Output:
- true
- Explanation:
10 is in the bottom row, second column, so the answer is true.
Example 2
- Input:
- grid = [[2,5,9],[4,7,12],[6,10,15]], target = 8
- Output:
- false
- Explanation:
8 would sit between 7 and 9 but no cell contains it, so the answer is false.
Example 3
- Input:
- grid = [[3]], target = 3
- Output:
- true
- Explanation:
A single-cell grid whose only value is the target.
Constraints
1 ≤ grid.length, grid[0].length ≤ 2000
-109 ≤ grid[i][j], target ≤ 109
Each row is sorted in ascending order and each column is sorted in ascending order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m + n)
- Space
- O(1)