How Do You Find the Kth Largest Element in an Array?
Learn quickselect for finding the kth largest element in average O(n) time, plus the min-heap alternative for streams.
Expected Interview Answer
The kth largest element can be found in average O(n) time using quickselect, a partition-based algorithm derived from quicksort that only recurses into the side of the partition containing the target rank, avoiding a full sort.
Quickselect partitions the array around a pivot exactly like quicksort, but after partitioning it checks whether the pivot's final index matches the target rank; if so it is done, otherwise it recurses only into the half that contains the rank, discarding the other half entirely. Because only one side is ever explored, the expected work shrinks geometrically, giving average O(n) time versus O(n log n) for a full sort. The worst case is O(n²) with a poor pivot, fixed in practice with random or median-of-medians pivot selection, the latter guaranteeing worst-case O(n). A simpler, still-common alternative is a fixed-size min-heap of size k, giving O(n log k) time and O(k) space, which is preferable when k is small or the data is streaming.
- Average O(n) time, faster than sorting
- In-place, O(1) extra space (excluding recursion stack)
- Heap variant handles streaming data with O(n log k)
- Median-of-medians pivot guarantees worst-case O(n)
AI Mentor Explanation
Finding the third-fastest bowling speed recorded all season is like quickselect: pick one recorded speed as a reference, sort everyone into faster-or-slower piles around it in one pass, then only dig into whichever pile actually contains the rank you want, throwing the other pile away completely. If the reference speed happens to land exactly at rank three, you're done immediately without touching the discarded pile at all. Because you only ever explore one shrinking pile instead of fully ranking every recorded delivery, the season's data resolves in far less work than sorting the whole list of speeds.
Step-by-Step Explanation
Step 1
Pick a pivot and partition
Rearrange the array in place so smaller elements are on one side of the pivot and larger on the other.
Step 2
Compare pivot rank to target k
If the pivot's final index equals the target rank, it is the answer; stop.
Step 3
Recurse into one side only
If the rank is less than the pivot index, recurse left; otherwise recurse right, discarding the other side entirely.
Step 4
Alternative: fixed-size min-heap
Maintain a min-heap of size k over the stream; the heap top is the kth largest, in O(n log k) time.
What Interviewer Expects
- Explain quickselect's partition-then-recurse-one-side logic
- State the average O(n) and worst-case O(n²) complexities
- Mention random or median-of-medians pivots to avoid worst case
- Know the O(n log k) min-heap alternative and when to prefer it
Common Mistakes
- Recursing into both partitions instead of only the one containing the rank
- Confusing kth largest with kth smallest and inverting the comparison
- Not knowing the O(n log k) heap alternative for streaming data
- Assuming quickselect is always O(n) without acknowledging the O(n²) worst case
Best Answer (HR Friendly)
“I use quickselect, which is like quicksort but only ever explores the half of the array that could contain the answer, throwing away the other half completely. That gives average linear time instead of the O(n log n) a full sort would cost, and for streaming data I would use a small min-heap of size k instead.”
Code Example
import random
def find_kth_largest(nums, k):
target = len(nums) - k # convert to 0-indexed kth smallest position
def partition(lo, hi):
pivot_idx = random.randint(lo, hi)
nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
pivot = nums[hi]
i = lo
for j in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[hi] = nums[hi], nums[i]
return i
lo, hi = 0, len(nums) - 1
while lo <= hi:
p = partition(lo, hi)
if p == target:
return nums[p]
elif p < target:
lo = p + 1
else:
hi = p - 1Follow-up Questions
- How would you guarantee worst-case O(n) instead of average O(n)?
- How would you find the k largest elements in a continuous data stream?
- When would a min-heap of size k be preferable to quickselect?
- How would you handle duplicate values when finding the kth largest?
MCQ Practice
1. What is the average-case time complexity of quickselect?
Because only one side of each partition is recursed into, the expected work shrinks geometrically to O(n).
2. What is quickselect's worst-case time complexity, and why?
A consistently bad pivot causes highly unbalanced partitions, degrading quickselect to O(n²) in the worst case.
3. What is the time complexity of using a fixed-size min-heap of size k to find the kth largest element in a stream?
Each of the n elements may trigger an O(log k) heap push/pop against the size-k heap, giving O(n log k) total.
Flash Cards
What algorithm finds the kth largest element in average O(n)? — Quickselect, a partition-based recursive selection algorithm.
Why is quickselect faster than sorting for this problem? — It only recurses into the partition containing the target rank, discarding the other half.
What is quickselect's worst-case complexity? — O(n²), with consistently poor pivot selection; mitigated with random or median-of-medians pivots.
What is the streaming-friendly alternative to quickselect? — A fixed-size min-heap of size k, giving O(n log k) time and O(k) space.