389. Kth in the Sorted Grid
A contest scoreboard is a grid of scores in which every row is sorted from left to right and every column is sorted from top to bottom. The same score may appear in several cells.
Given the grid grid and an integer k, return the k-th smallest score in the whole grid, counting duplicates (so in [1, 1, 2] the 2nd smallest is 1). The grid is too big to flatten and sort comfortably, so look for something that uses the sorted rows and columns: it should take O(n * log(range)) time for an n-by-n grid and only O(1) extra space.
Example 1
- Input:
- grid = [[1,4,9],[3,6,12],[5,8,15]], k = 4
- Output:
- 5
- Explanation:
In order the scores are 1, 3, 4, 5, 6, ..., so the 4th smallest is 5.
Example 2
- Input:
- grid = [[2,2],[2,2]], k = 3
- Output:
- 2
- Explanation:
All scores are 2, so the 3rd smallest is 2.
Constraints
1 ≤ grid.length, grid[0].length ≤ 500
-109 ≤ grid[i][j] ≤ 109
Rows and columns are sorted in non-decreasing order.
1 ≤ k ≤ grid.length * grid[0].length
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((m + n) log R), where R is the value range
- Space
- O(1)