Problem Statement

Return the k most frequent elements in the array.

Why This Problem Matters

• Tests ability to trade space for time using buckets or heaps.
• Common question to evaluate knowledge of frequency counting patterns.
• Variants appear in streaming analytics and search ranking problems.

Thought Process

Step-by-Step Reasoning

1. Count frequencies using a map.
2. Create buckets array where index = frequency, storing numbers with that count.
3. Iterate from buckets.length - 1 down collecting numbers until k reached.
4. Return result list.

Dry Run

Complexity Analysis

Annotated Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TopKFrequentElements {
  public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
      freq.merge(num, 1, Integer::sum);
    }

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

    int[] result = new int[k];
    int idx = 0;
    for (int i = buckets.size() - 1; i >= 0 && idx < k; i -= 1) {
      for (int num : buckets.get(i)) {
        if (idx < k) {
          result[idx++] = num;
        }
      }
    }
    return result;
  }
}

Frequency buckets group numbers by occurrence count, enabling linear-time selection of highest frequencies.

Common Pitfalls

• Forgetting to size buckets to nums.length + 1 results in index errors.
• Min-heap approach must evict when size exceeds k; missing this returns wrong results.
• Order of returned elements can be arbitrary unless additional sorting applied.

Follow-Up Questions

• How do you handle streaming data where n is massive? (Use size-k heap or reservoir sampling.)
• Can you solve the top-k frequent words variant requiring lexicographic ordering?

Key Takeaways