Top K Elements

Top K Frequent

First, count frequencies with a hash map. Then add (frequency, element) pairs to a min-heap of size K. Elements with higher frequency push out lower-frequency ones. Final heap = K most frequent elements.

O(n log k)

O(n)

say this out loud

Count first, then a size-K heap over the counts. If K is close to n I bucket by frequency instead and it drops to O(n).

How It Works

Top K frequent elements combines a hash map with a bounded heap. First pass: count occurrences of every element in a frequency map, O(n). Second pass: push (frequency, element) pairs into a min-heap keyed by frequency, capping the size at K, when the heap is full and a new pair's frequency exceeds the top's, evict the top. The survivors are the K most frequent elements.

The heap phase costs O(m log K), where m is the number of distinct elements, so the total is O(n + m log K). Better than sorting all frequency pairs at O(m log m) when K is small. When frequencies matter more than order, bucket sort offers an O(n) alternative: index buckets by frequency (which is at most n) and read them from the highest down until K elements are collected.

Step-by-Step Visualization

Top 2 most frequent in [1, 1, 1, 2, 2, 3], using a heap rather than buckets

1/7

Code

Java

static int[] topKFrequent(int[] nums, int k) {
  Map<Integer, Integer> freq = new HashMap<>();
  for (int n : nums) freq.merge(n, 1, Integer::sum);

  return freq.entrySet().stream()
    .sorted((a, b) -> b.getValue() - a.getValue())
    .limit(k)
    .mapToInt(Map.Entry::getKey)
    .toArray();
}

Tips & Gotchas

1Count frequencies first, then use min-heap of size K

2Heap stores (frequency, element) pairs

3After processing all elements, heap contains top K frequent

Practice Problems

1Top K Frequent Elements
2Top K Frequent Words
3Sort Characters by Frequency
4Kth Largest Element in an Array

About the Top K Elements Pattern

Use a min-heap of size K. As you process elements, if the current element is larger than the heap's minimum, swap it in. When done, the heap contains exactly the K largest elements. The top is the Kth largest.

Key insight

Need the K largest? Use a min-heap of size K. Anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.

Common Heap Interview Problems

Kth Largest Element
Top K Frequent Elements
Find Median from Data Stream
Merge K Sorted Lists
Task Scheduler
K Closest Points to Origin

Frequently Asked Questions

When is bucket sort better than a heap here?

Frequencies are bounded by n, so placing each distinct element into a bucket indexed by its count and scanning buckets from high to low is O(n) total, beating the heap's O(n + m log K). The heap wins when input is a stream, memory is tight, or ties must break by a secondary key like alphabetical order.

How are ties handled, as in Top K Frequent Words?

Make the heap comparator two-dimensional: primary key frequency, secondary key the tie-break rule. For a min-heap keeping the best K words, that means lowest frequency first and, among equals, lexicographically largest first, so the correct candidate is the one evicted.