Kth Largest Element in an Array medium
Description
Given an integer array nums and an integer k, return the kth largest element. Note that it’s the kth largest in sorted order, not the kth distinct.
Examples
> Case 1:
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
> Case 2:
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4Constraints
1 <= k <= nums.length <= 10^5- Aim for better than O(n log n) if you can.
Three approaches in order of cleverness
This is the rare interview problem with three legitimate solutions, each better than the last. Being able to articulate the trade-offs is the point.
Approach 1: Sort and index
The dumbest correct answer. Sort, then return nums[n - k].
def find_kth_largest(nums, k):
nums.sort()
return nums[-k]Time: O(n log n), Space: O(1) (or O(log n) for sort’s stack). Always works. Always slow.
Approach 2: Min-heap of size k
Maintain a min-heap with the k largest elements seen so far. For each new element:
- If the heap has fewer than
kelements, push. - Otherwise, if the new element is larger than the heap’s minimum, pop the min and push the new element.
After processing every element, the heap holds the k largest, and the smallest of those (the heap root) is the kth largest in the whole array.
Time: O(n log k) — much better than O(n log n) when k is small. Space: O(k).
This is the answer most interviewers expect — clean, generalizes beautifully (“top K anything”).
Approach 3: Quickselect (the interview gold standard)
Partitioning ideas from quicksort, but only recurse into the side that contains rank n - k. This brings the expected runtime down to O(n).
Pick a pivot, partition into [< pivot] [pivot] [> pivot].
If pivot's final position equals our target rank → return it.
If our target rank is in the left side → recurse there only.
If in the right side → recurse there only.Each call cuts the problem in half (on average), so:
T(n) = T(n/2) + O(n) → T(n) = O(n)(Versus quicksort’s T(n) = 2·T(n/2) + O(n) = O(n log n), because quicksort has to recurse on both sides.)
Always randomize the pivot. Without randomization, an adversarial input (already sorted, all duplicates) sends quickselect to O(n²). The one-line random swap fixes it.
Analysis comparison
| Approach | Time (avg) | Time (worst) | Space | When to use |
|---|---|---|---|---|
| Sort + index | O(n log n) | O(n log n) | O(1) | If clarity beats speed. |
| Min-heap (k) | O(n log k) | O(n log k) | O(k) | Standard interview answer. Streams. |
| Quickselect | O(n) | O(n²) without random pivot | O(log n) avg | Gold standard. Mention this. |
Which one in an interview?
Walk all three. Start with sorting (the obvious one), then offer the heap solution (better when k << n), then mention quickselect as the optimal O(n) answer. Demonstrating you know the progression of solutions matters more than just landing on quickselect immediately.