grid is a rectangular list of integer lists where every row is sorted in ascending order and every column is sorted in ascending order. Return the k-th smallest value in the grid, counting duplicates separately (the 2nd smallest of [[1, 2], [1, 3]] is 1).
Examples
Input: grid = [[1, 4, 7],
[2, 5, 8],
[3, 6, 9]], k = 5
Output: 5
Input: grid = [[1, 2],
[1, 3]], k = 2
Output: 1
Constraints
1 <= rows, cols <= 1000,rows * cols <= 10**5, values in[-10**9, 10**9]1 <= k <= rows * cols- Target complexity: O(k log(min(k, rows))).
Goals
- Treat each sorted row as a stream and merge them with a heap
- Seed with only as many rows as k requires
- Stop after exactly k extractions