Baseline Heaps · Medium Problems O(n log k) · O(k)
A warehouse scanner reads package weights one aisle at a time, and logistics wants the kth-lightest weight without a full sort. A holding bin keeps the k lightest weights seen so far, expelling its heaviest resident whenever a lighter package shows up. When the scan finishes, the bin's heaviest resident is exactly the kth-lightest weight.
Input: An integer array arr of distinct values and an integer K.
Output: Return the Kth smallest element of arr.
1 <= K <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9All array elements are distinctInput: {"arr":[7,10,4,3,20,15],"K":3}
Output: 7
The values below 7 are 3 and 4, so 7 is the third-smallest.
Input: {"arr":[7,10,4,3,20,15],"K":4}
Output: 10
Exactly three values (3, 4, 7) rank below 10.