Challenge
Return the kth item if all elements were sorted from largest to smallest. Duplicate values occupy separate ranks. For example, the second largest of [7, 7, 2] is 7, not 2. Aim to retain only k candidates.
Input and output contract
1 ≤ n ≤ 100,000; 1 ≤ k ≤ n; integer elements with absolute value ≤ 1,000,000.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from kth_largest; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log(k + 1)) time; O(k) auxiliary space
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[3, 2, 3, 1, 2, 4, 5, 5, 6], 4]
Expected return
4
Arguments
[[7, 7, 2], 2]
Expected return
7
Arguments
[[-9, -4, -7], 3]
Expected return
-9
Hint
Keep a min-heap containing the k largest values seen. Its root is the kth largest.
The worked solution unlocks after completion, or with Premium access.