Frequency Count

Top K Frequent

Step 1: Count frequencies with a hash map. Step 2: Find the K highest frequencies using a min-heap of size K (or bucket sort by frequency for O(n)). This avoids sorting the entire frequency list.

O(n)

How It Works

Top K Frequent Elements is a two-phase problem: count, then select. Phase one builds a hash map from element to frequency in O(n). Phase two picks the k largest frequencies without sorting everything: push entries through a min-heap capped at size k, evicting the smallest whenever the heap overflows, for O(n log k) total. The heap's root is always the weakest current candidate, so anything beating it belongs in the top k.

Bucket sort does even better: since no frequency can exceed n, place each element into bucket[frequency] and read buckets from n down to 1 until k elements are collected. That achieves O(n) time, beating the O(n log n) full-sort baseline.

Step-by-Step Visualization

Find top 2 frequent elements

Freq{1:3, 2:2, 3:1}

Frequencies

1 3 times

2 2 times

3 1 time

1/3

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);

  List<Integer>[] buckets = new List[nums.length + 1];
  for (int i = 0; i < buckets.length; i++) buckets[i] = new ArrayList<>();
  for (Map.Entry<Integer, Integer> e : freq.entrySet()) buckets[e.getValue()].add(e.getKey());

  List<Integer> result = new ArrayList<>();
  for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--)
    result.addAll(buckets[i]);
  return result.stream().mapToInt(Integer::intValue).toArray();
}

Tips & Gotchas

1Bucket sort approach: index = frequency, value = list of elements

2Count frequencies, then iterate buckets from high to low

3Alternative: use a min-heap of size K

Practice Problems

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

About the Frequency Count Pattern

Count how often each element appears, then use those counts to answer questions like 'what's the most common?', 'are there duplicates?', or 'what appears more than n/2 times?'

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

Why a min-heap of size k rather than a max-heap of everything?

A max-heap over all m distinct elements costs O(m) space and O(m + k log m) to extract, while the size-k min-heap keeps only the current best k candidates in O(k) space with O(n log k) work. For small k relative to n, the min-heap is decisively cheaper.

When does bucket sort beat the heap approach?

Bucket sort achieves true O(n) because frequencies are bounded by the array length, making it ideal when k can be large. The heap remains attractive for streaming scenarios or when a comparator must break ties, as in Top K Frequent Words with alphabetical ordering.