Loading
Loading
A warehouse stores crates on a rectangular grid of shelves. Crate weights increase from left to right along every row and from front to back along every column. An auditor wants to inspect the k-th lightest crate.
Given grid, where every row and every column is sorted in non-decreasing order, and an integer k, return the k-th smallest value in the whole grid. Repeated values each count separately.
grid = [[1, 5, 9], [3, 6, 12], [7, 10, 14]], k = 5heap = {1, 3, 7}the front of every rowpop 1 (1st)push 5, the next value in row 0pop 3 (2nd)push 6 from row 1pop 5 (3rd)push 9 from row 0pop 6 (4th)push 12 from row 1heap root = 7four values removed, so the root is the 5th smallest7Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 5 | 9 |
|---|---|---|---|
| 1 | 3 | 6 | 12 |
| 2 | 7 | 10 | 14 |
In order: 1, 3, 5, 6, 7, 9, 10, 12, 14. The fifth is 7.
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(r + k log r) time · O(r) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 5 | 9 |
|---|---|---|---|
| 1 | 3 | 6 | 12 |
| 2 | 7 | 10 | 14 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Example 2
| 0 | 2 | 2 |
|---|---|---|
| 1 | 2 | 4 |
Repeated values each count: 2, 2, 2, 4, so the third is 2.