Efficiently find the k largest, smallest, or most frequent elements using heaps.
The Top K Elements pattern uses a heap (priority queue) to maintain the top k elements as you scan through data. Instead of sorting the entire array, you keep a small heap of size k, which gives you dramatic performance improvements when k is much smaller than n.
For k largest: use a min-heap of size k. The smallest element in the heap acts as the gatekeeper. For k smallest: use a max-heap of size k. The largest element in the heap acts as the gatekeeper.
As each element arrives, add it to the heap. When the heap exceeds size k, remove the minimum. After processing all elements, the heap holds exactly the k largest values.
Finding the 3 largest elements from [3, 1, 5, 12, 2, 11] using a min-heap of size 3:
Why a min-heap for k largest? The min-heap's root is the smallest element among the current top k. Any new element larger than the root belongs in the top k, so we swap it in. Any element smaller cannot be in the top k, so we skip it. The root acts as a gatekeeper.
Look for these signals in the problem statement. Any of these phrases strongly suggest the Top K Elements pattern:
Why not just sort? Sorting gives O(n log n). With a heap of size k, you get O(n log k). When k is much smaller than n (e.g., k=10 and n=1,000,000), the difference is enormous. You also do not need the full sorted order — just the top k.
The simplest application. Maintain a min-heap of size k. After processing all elements, the root of the heap is the kth largest element.
We want the 3rd largest element. Sorted: [1, 2, 3, 4, 5, 6]. Answer = 4.
// LeetCode #215 — Kth Largest Element in an Array public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); // evict the smallest } } return minHeap.peek(); // root = kth largest }
Invariant: After processing each element, the heap contains the k largest elements seen so far. The root is always the kth largest. This invariant is what makes the pattern so elegant.
First count frequencies with a HashMap. Then find the k most frequent elements. Two approaches: heap-based (general) and bucket sort (O(n) optimal).
Build a frequency map, then use a min-heap of size k on (element, frequency) pairs. The heap orders by frequency, keeping the k most frequent.
// LeetCode #347 — Top K Frequent Elements (Heap) public int[] topKFrequent(int[] nums, int k) { // Step 1: Count frequencies Map<Integer, Integer> freq = new HashMap<>(); for (int n : nums) freq.merge(n, 1, Integer::sum); // Step 2: Min-heap of size k, ordered by frequency PriorityQueue<int[]> heap = new PriorityQueue<>( (a, b) -> a[1] - b[1] ); for (var entry : freq.entrySet()) { heap.offer(new int[]{entry.getKey(), entry.getValue()}); if (heap.size() > k) heap.poll(); } // Step 3: Extract results int[] result = new int[k]; for (int i = 0; i < k; i++) result[i] = heap.poll()[0]; return result; }
Use the frequency as the bucket index. Since the maximum frequency is n, create an array of n+1 buckets. Elements with the same frequency go into the same bucket. Iterate buckets from highest to lowest.
// LeetCode #347 — Top K Frequent Elements (Bucket Sort) public int[] topKFrequent(int[] nums, int k) { // Step 1: Count frequencies Map<Integer, Integer> freq = new HashMap<>(); for (int n : nums) freq.merge(n, 1, Integer::sum); // Step 2: Create buckets indexed by frequency List<Integer>[] buckets = new List[nums.length + 1]; for (var entry : freq.entrySet()) { int f = entry.getValue(); if (buckets[f] == null) buckets[f] = new ArrayList<>(); buckets[f].add(entry.getKey()); } // Step 3: Collect from highest frequency down int[] result = new int[k]; int idx = 0; for (int i = buckets.length - 1; i >= 0 && idx < k; i--) { if (buckets[i] != null) for (int val : buckets[i]) if (idx < k) result[idx++] = val; } return result; }
Heap vs Bucket Sort: The heap approach works for any comparable metric and gives O(n log k). Bucket sort gives O(n) but only works when the "ranking value" (frequency) has a bounded range. In interviews, knowing both approaches demonstrates depth.
The general template for Top K Elements problems. Memorize this pattern and adapt it to specific problems.
// Template: Top K Elements using Min-Heap // Finds the k largest elements (or kth largest) PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); // evict smallest } } // minHeap.peek() = kth largest element // Heap contents = top k largest elements return minHeap.peek();
// For custom objects: use comparator on the ranking metric // Example: K closest points to origin PriorityQueue<int[]> maxHeap = new PriorityQueue<>( (a, b) -> dist(b) - dist(a) // max-heap by distance ); for (int[] point : points) { maxHeap.offer(point); if (maxHeap.size() > k) { maxHeap.poll(); // evict farthest } } // Heap contains k closest points
These are the classic Top K Elements problems you should practice:
Study order: Start with #215 (pure heap template), then #347 (frequency + heap), then #692 (adds tie-breaking logic), and finally #373 (multi-source heap expansion).
Enter an array and a value for k. Watch the min-heap maintain size k as elements are processed one by one.
We process each of the n elements once. Each heap insertion/removal costs O(log k) since the heap never exceeds size k. Total: O(n log k). The heap stores at most k elements, so space is O(k).
When k is small: log k is nearly constant. For k=10 and n=1,000,000, the heap approach does ~3.3 million comparisons versus ~20 million for full sort. The heap approach also works on streams of data where you cannot access the full dataset at once.