378. Search the Flat Grid
A seating chart of a stadium lists ticket numbers in rows. Each row is sorted from left to right, and the first number of every row is larger than the last number of the row above it, so reading the rows one after another gives one long increasing sequence.
Given the grid grid and an integer target, return true if the grid contains target and false otherwise. The grid can have hundreds of thousands of cells, so your solution must run in O(log(m * n)) time for a grid with m rows and n columns.
Example 1
- Input:
- grid = [[2,6,11,14],[17,21,25,31],[36,40,44,58]]target = 25
- Output:
- true
- Explanation:
The value 25 sits in the second row, third column.
Example 2
- Input:
- grid = [[2,6,11,14],[17,21,25,31],[36,40,44,58]]target = 30
- Output:
- false
- Explanation:
No cell holds 30, so the answer is false.
Constraints
1 ≤ m, n ≤ 1000
-109 ≤ grid[i][j], target ≤ 109
Each row is sorted in increasing order, and grid[i][0] > grid[i - 1][n - 1] for every i > 0.
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 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log(m * n))
- Space
- O(1)