#215
Kth Largest Element in an Array
Medium Min-heap / quickselect
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the k-th largest element of an unsorted array (by sorted position, so duplicates count).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k-th largest value in an unsorted array.
Why this works: a min-heap of size k keeps the k largest; its top is the answer.
Example: [3, 2, 1, 5, 6, 4], k = 2
heap ends as {5, 6} → top 5✦Hints open one at a time
A min-heap of size k gives O(n log k).
Quickselect partitions like quicksort but recurses into one side only: average O(n).
↗Approach
Keep a min-heap of at most k elements; after scanning, its top is the answer. (Quickselect is the follow-up; use a random pivot to avoid worst cases.)
</>Solution (Java)
import java.util.*;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll(); // keep the k largest
}
return heap.peek();
}
}!Common mistake
Treating it as "k-th largest distinct value" and removing duplicates.
Complexity
- Time: O(n log k).
- Space: O(k).
Topic: Heaps & Priority Queue
🎬 Episodes 64–68: video coming soon