Loading
Loading
A noise monitor on a construction site records a decibel reading every minute. The site manager does not care about the single loudest spike, which is often a fluke. She wants the k-th loudest reading of the shift.
Given the list readings and an integer k, return the value that would sit in position k if the readings were ordered from loudest to quietest. Repeated values each take their own position.
readings = [62, 48, 75, 48, 90, 55], k = 2heap = [62]push 62; the heap keeps the 2 loudest seen so farheap = [48, 62]push 48heap = [62, 75]push 75; size 3, so pop the quietest (48)heap = [62, 75]48 enters and is popped straight awayheap = [75, 90]90 enters, 62 is evictedheap = [75, 90]55 enters and is evicted; the root 75 is the answer75Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
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(n log k) time · O(k) space
Input. Run your code to watch it work on this input, one line at a time.
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.
Ordered loudest first: 90, 75, 62, 55, 48, 48. The second is 75.
Example 2
Both 71s take their own position, so the second loudest is also 71.