Kth Largest Element in an Array medium
Description
Given an integer array nums and an integer k, return the k-th largest element in the array.
Note that it is the k-th largest element in the sorted order, not the k-th distinct element.
Can you solve it without sorting?
Examples
> Case 1:
nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
> Case 2:
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Solution 1 — Heap (the “easy” answer)
A min-heap of size k. Push everything, pop down to size k, and the root is the answer.
import heapq
def find_kth_largest(nums, k):
return heapq.nlargest(k, nums)[-1]O(n log k) time, O(k) space. Cleanest one-liner, but doesn’t hit the O(n) target.
Solution 2 — Quickselect (the D&C answer)
Adapt quicksort’s partition step: after partitioning, the pivot is in its final sorted position. If that position is the target, return the pivot. Otherwise recurse on only the half that contains the target.
- Divide: partition around a pivot.
- Conquer: recurse on the half containing the answer.
- Combine: nothing.
Recurrence (average): T(n) = T(n / 2) + O(n) → O(n) by case 3 of the Master Theorem.
Worst: T(n) = T(n - 1) + O(n) → O(n²) (e.g., always-bad pivot).
Random pivot is essential. Without it, sorted (or reverse-sorted) input gives O(n²). The Python version above does this; the C++ / Java versions use the last element as pivot for clarity, which has the same worst case. In a real interview, mention the random-pivot variant explicitly.
Solution 3 — Median of Medians (the O(n) guarantee)
If you need O(n) worst case (not just average), use median-of-medians to pick the pivot. It guarantees a pivot that’s between the 30th and 70th percentile, which gives T(n) <= T(n/5) + T(7n/10) + O(n) = O(n) by Akra-Bazzi.
In practice, randomized quickselect is faster — median-of-medians is for theoretical guarantees only.
Analysis
| Approach | Time average | Time worst | Space |
|---|---|---|---|
| Heap | O(n log k) | O(n log k) | O(k) |
| Quickselect | O(n) | O(n²) | O(log n) avg |
| Sort + index | O(n log n) | O(n log n) | O(1)-ish |
| Median of medians | O(n) | O(n) | O(log n) |
Same skin
- Top K Frequent Elements — quickselect over frequency counts.
- K Closest Points to Origin — quickselect by distance.
- Median of an Unsorted Array —
k = n / 2quickselect. - Wiggle Sort II — quickselect plus a reorder step.