Find the Kth Highest Reading in a Sensor Batch
Solve this ProblemA batch of sensor readings arrives as an unordered list. Report the k-th highest reading — the value that would sit in position k if the readings were sorted from highest to lowest. Repeated readings occupy separate positions, so a reading that appears twice can hold two ranks.
Sorting the whole batch answers the question but orders far more than is needed. A min-heap capped at k entries keeps exactly the k highest readings seen so far, with the k-th highest always sitting at its root.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ k ≤ readings.length ≤ 100 - ◆
-1000 ≤ readings[i] ≤ 1000 - ◆
Readings may repeat; a repeated value counts once for every time it appears when ranking (the ranking is by position in the sorted order, not by distinct values)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Sort Everything and Index From the End
BruteCopy the readings, sort the copy in ascending order, and read the element k positions from the end. Simple and correct, but it fully orders all n readings just to look at a single position — every element is placed exactly, though only the k-th highest matters.
O(n log n)O(n)1class Solution {
2 public int kthHighestReading(int[] readings, int k) {
3 int[] sorted = readings.clone();
4 Arrays.sort(sorted);
5 return sorted[sorted.length - k];
6 }
7}Optimal — Size-k Min-Heap of the Best Readings So Far
OptimalKeep a min-heap that never holds more than k readings — the k highest seen so far. Its root is the smallest of those k, which is exactly the current k-th highest. A new reading is added while the heap has fewer than k entries; after that it only matters if it beats the root, in which case it replaces the root (the old k-th highest can no longer be in the top k). After the last reading, the root is the answer. Each heap operation costs O(log k) rather than O(log n), and only k values are ever stored.
O(n log k)O(k)1class Solution {
2 public int kthHighestReading(int[] readings, int k) {
3 PriorityQueue<Integer> smallest = new PriorityQueue<>();
4 for (int reading : readings) {
5 if (smallest.size() < k) {
6 smallest.offer(reading);
7 } else if (reading > smallest.peek()) {
8 smallest.poll();
9 smallest.offer(reading);
10 }
11 }
12 return smallest.peek();
13 }
14}