Top K Elements Pattern

CodingMid2 min read · 5 problemsUpdated Oct 28, 2026

Maintain a heap of size k to track the k largest/smallest/most-frequent elements.

When to Use It

K largest/smallest, k closest points, k most frequent, kth-X in a stream.

Classic example: Top K frequent elements.

How It Works

Maintain a heap of size k. For 'top k largest', use a min-heap, when its size exceeds k, pop the smallest, keeping only the k largest seen so far. Pushing all n elements gives O(n log k): strictly better than sorting (O(n log n)) when k << n, and easily streamable since you only ever hold k items.

Quickselect is the alternative when you can mutate the input array and want average O(n): partition like quicksort but only recurse into the side containing the kth element. Worst case is O(n^2), mitigated by random pivot selection (or median-of-medians for guaranteed O(n), though that's rarely worth it in interviews).

For 'k most frequent' problems, combine with a hash map (count occurrences) then run top-k on the count map. Bucket sort is an O(n) alternative when counts are bounded by n: bucket[count] = list of values with that count, then walk buckets from high to low.

Key Insight

A size-k heap turns 'top k of n elements' from O(n log n) into O(n log k), and crucially makes the problem streamable, you only ever hold k items in memory regardless of n.

Maintain a heap of size k. Each new element replaces the heap's min iff it's larger.

Worked Example

Top K frequent elements

nums = [1, 1, 1, 2, 2, 3, 4, 4, 4, 4], k = 2

Count first: 1 appears 3 times, 2 twice, 3 once, and 4 four times
Push 1 (count 3): heap holds 1
Push 2 (count 2): heap holds 2 and 1
Push 3 (count 1): heap is over size 2, so pop the smallest count, 3
Push 4 (count 4): heap is over size 2, so pop the smallest count, 2. Heap holds 1 and 4

Result: [4, 1]. The min-heap never grows past k, so each push and pop costs O(log k), and the root is always the weakest candidate still in the running.

Templates

// import java.util.*;
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of size k
for (int num : nums) {
    heap.offer(num);
    if (heap.size() > k) heap.poll();
}
// heap now holds the k largest elements; heap.peek() is the kth largest

import heapq

heap = []  # min-heap of size k
for num in nums:
    heapq.heappush(heap, num)
    if len(heap) > k:
        heapq.heappop(heap)
# heap now holds the k largest elements; heap[0] is the kth largest

Common Pitfalls

Using a max-heap for 'top k largest' and popping after inserting all n elements: works but is O(n log n), defeating the purpose; the right choice is a min-heap of size k.
For 'k closest points to origin', forgetting that you can compare squared distances and avoid sqrt entirely.
In quickselect, recursing on both sides instead of only the one containing k, losing the O(n) average.
For 'k most frequent', sorting all counts when bucket sort gives O(n) and a heap of size k gives O(n log k).
Returning the heap directly without sorting when the problem requires the top k in order.

When It Breaks

When k is close to n, a size-k heap saves almost nothing over sorting everything in O(n log n), and sorting is simpler to get right.
Frequencies can't exceed n, so bucketing elements by count gives O(n) for top-k-frequent with no heap at all.
Quickselect finds the k-th element in O(n) on average, but it's O(n^2) in the worst case and needs the whole input in memory. For a stream, the size-k heap is the tool that works.

Variations

Top k largest/smallest: min-heap or max-heap of size k respectively.
K most frequent elements: hash map + heap of size k, or bucket sort.
K closest points to origin: heap of size k keyed by squared distance.
Kth largest in a stream: heap of size k, with O(log k) updates per insert.
Quickselect: partition-based, average O(n) but requires in-place mutation.

Big O

Time: O(n log k)
Space: O(k)

Each of n elements does at most one push and one pop on a size-k heap, each costing log k. The heap itself never exceeds size k.

Next PatternK-Way Merge