The O(n) Club: Top K Frequent Elements—How to Nail This Without Sorting Yourself Into Oblivion

The O(n) Club: Top K Frequent Elements—How to Nail This Without Sorting Yourself Into Oblivion

⚡ TL;DR

Given an array, return the k most frequent elements. If you just sort the whole frequency map, your code will run about as fast as dial-up—don’t. See a typical rookie move:

// Painfully slow O(n log n)
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);
return freq.entrySet().stream()
    .sorted((a, b) -> b.getValue() - a.getValue())
    .limit(k)
    .map(Map.Entry::getKey)
    .toArray(Integer[]::new);

🧠 How Devs Usually Mess This Up

Every dev’s lizard brain thinks: “Count, then just sort by frequency!” But that’s O(n log n)—enough to make your interviewer’s face do the disappointed parent look. Some bonus blunders:

• Cramming every number into a max-heap instead of tracking just k elements. Classic ‘bring a bazooka to a pillow fight’ energy.
• Fretting about the output order (the question literally doesn’t care—save your perfectionism for naming variables).
• Worrying about duplicates in the output; trust your HashMap, like you trust your favorite debugging snack.

🔍 What’s Actually Going On

This is the Interviewer’s Favourite: “Do they use the right tools, or do they panic and sort everything?”
All you really need is:

• Counting frequencies—use a HashMap like a civilized Java developer.
• Finding the top ‘k’—without sorting the entire planet.

Your two MVPs are:

• Bucket Sort: You can’t have a number appear more than n times, so use an array of lists (buckets). Buckets[i] = all numbers seen i times. Start from the end—just scoop up k numbers. Efficiency so beautiful it should be in a museum.
• Min-Heap (size k): Walk through the frequency map, always keeping the smallest frequency at the top. Heap gets too big? Eject the least frequent. At the end, pop out your top k. It’s like a velvet rope for your array’s VIPs.

🛠️ PseudoCode

• Build the frequency map:

  Map<Integer, Integer> freq = new HashMap<>();
  for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);

  HashMap magic: count each number in O(1) time per update.

• Do the bucket sort:

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

  Buckets index = frequency. Fill them up!

• Pick the top k from high frequencies down:

  List<Integer> res = new ArrayList<>();
  for (int i = buckets.length - 1; i >= 0 && res.size() < k; i--) {
      if (buckets[i] != null) res.addAll(buckets[i]);
  }
  return res.subList(0, k);

  Scoop k goodies from the highest buckets—no sorting, no tears.

💻 The Code

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);
    List<Integer>[] buckets = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        int cnt = entry.getValue();
        if (buckets[cnt] == null) buckets[cnt] = new ArrayList<>();
        buckets[cnt].add(entry.getKey());
    }
    List<Integer> res = new ArrayList<>();
    for (int i = buckets.length - 1; i >= 0 && res.size() < k; --i) {
        if (buckets[i] != null) res.addAll(buckets[i]);
    }
    int[] result = new int[k];
    for (int i = 0; i < k; ++i) result[i] = res.get(i);
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All elements unique? Your buckets will be lonely but the code still works.
• k equals array length? Just hand over every number—skip the drama.
• Time/Space: Counting O(n), bucketing O(n), collecting O(n). Total O(n) time, O(n) extra space. Passes the “Big Input, Small Panic” interview test.
• Don’t overthink ties or return order. Interviewer doesn’t care (see problem statement).

🧠 Interviewer Brain-Tattoo

“If you sort the frequency map, you’re working way too hard—it’s like alphabetizing your laundry before washing it. Use buckets or a min-heap, keep your runtime (and dignity) intact.”