Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the k-th largest value in the array, counting duplicates as separate entries. In other words, if the array were sorted in descending order, return the element at position k (1-indexed). Do not assume the values are distinct.

• Up to around a hundred thousand elements, and k is always a valid rank for the given array.
• Values fit comfortably in a normal int, positive or negative.

Examples

• nums = [7,1,9,4,2,8], k = 3 → 7. Sorted descending: 9, 8, 7, ... and the third entry is 7.
• nums = [7,4,7,1,4,9,8,8,2], k = 5 → 7. Descending: 9, 8, 8, 7, 7, ...; duplicates count, so the 5th is the second 7, not 4.
• nums = [6], k = 1 → 6. A single element is both the largest and the smallest.

Hints

1. Sorting gives the answer in O(n log n). Do you actually need the whole array in order, or just to know which elements are among the top k?
2. Keep a small collection of the best k seen so far. Which structure lets you evict the weakest of them cheaply?
3. Min-heap of size k for O(n log k), or quickselect (partition around a random pivot, recurse into one side) for O(n) average.