K-th Largest Item

Write kth_largest(nums, k) that returns the value that would be in place k if nums were ranked from largest to smallest. Equal values take separate places: in [5, 5, 3] the largest is 5, the 2nd largest is also 5, and the 3rd largest is 3.

Examples

kth_largest([3, 9, 1, 7, 5], 2)      # returns 7
kth_largest([4, 4, 2, 8, 8, 8], 3)   # returns 8
kth_largest([-5, -2, -9], 3)         # returns -9

In the second example the three 8s take places 1, 2 and 3.

Constraints

• 1 <= k <= len(nums) <= 100,000
• -10^9 <= nums[i] <= 10^9

Note

Sorting the whole list works. For a stretch, find the answer in one pass while keeping at most k values in memory, which pays off when the list is huge and k is small.