K-th Loudest Reading
EasyHeap / Priority QueueFree
Problem
A noise sensor logged a list of decibel readings. Return the k-th loudest reading: the value that would sit at position k if the readings were sorted from loudest to quietest.
Repeated values count separately, so in [71, 71, 62] both the 1st and the 2nd loudest readings are 71.
Example 1
- Input:
- readings = [62, 71, 55, 90, 71], k = 2
- Output:
- 71
Sorted loudest first: 90, 71, 71, 62, 55. Position 2 holds 71.
Example 2
- Input:
- readings = [40, 40, 40], k = 3
- Output:
- 40
Constraints
- 1 ≤ k ≤ readings.length ≤ 10^5
- -10^4 ≤ readings[i] ≤ 10^4
Hint
Show the first hint
You do not need the whole order, only the k loudest values seen so far.
Walkthrough
How to approach it
01Clarify before coding
- Do duplicates count as separate positions? Yes: [71, 71, 62] has 71 as both 1st and 2nd loudest.
- Is k always valid? Yes, 1 ≤ k ≤ n, so there is always an answer.
- Can readings be negative? Yes; nothing in the approach depends on sign.
02Brute force
Sort the readings in descending order and return the element at index k - 1.
Cost: O(n log n) time and O(n) space for the sorted copy. Fine here, but it orders all n values when only k matter, and it needs the whole input in memory at once.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.