Top K Frequent Elements

Why it belongs on this sheet

Frequency problems show up often, and this one lets you discuss both heap and bucket-sort approaches.

Pattern

Frequency map plus buckets

Approach

Count each number first. Then place numbers into buckets indexed by frequency. Walk buckets from high to low until k answers are collected.

Java solution

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

class Solution {
  public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
      count.put(num, count.getOrDefault(num, 0) + 1);
    }

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

    int[] answer = new int[k];
    int index = 0;
    for (int frequency = buckets.length - 1; frequency >= 0 && index < k; frequency--) {
      if (buckets[frequency] == null) {
        continue;
      }
      for (int num : buckets[frequency]) {
        answer[index++] = num;
        if (index == k) {
          break;
        }
      }
    }

    return answer;
  }
}

Complexity

• Time: O(n)
• Space: O(n)

Interview note

If the interviewer prefers a heap, mention O(n log k) as the flexible alternative.