347. Top K Frequent Elements

The tidy answer to Top K Frequent Elements is a heap, and it passes — but the problem quietly dares you to do better than sorting, and that hint points at a slicker trick. It sits in the arrays and hashing pattern, where a frequency map plus one clever second step is the recurring shape.

The problem

Given an integer array and a number k, return the k values that show up most often. Order among them doesn’t matter. (Full statement on LeetCode.)

For nums = [5, 5, 5, 2, 2, 8] and k = 2, the answer is [5, 2] — 5 appears three times, 2 twice, and 8 loses out.

Intuition: bucket by frequency instead of sorting

Every approach starts the same way: sweep the array once and tally counts in a hash map. The real question is how you pull the top k out of that map.

Sorting the entries by count gets you there in $O(n \log n)$, but the follow-up asks for better — and there’s a structural fact to exploit. In an array of length n, no value can appear more than n times, so every frequency is an integer in the range $[1, n]$. When the thing you want to sort by is a small bounded integer, you don’t need comparisons at all. You can drop each value into a bucket indexed by its frequency, then read the buckets from the top down.

That’s the leap: bucket[f] holds every value seen exactly f times. Walk from the highest frequency downward, collect values until you have k, and you’re done in linear time. It’s counting sort wearing a different hat — trading the generality of comparison sorting for the speed you get when the key range is known.

Solution

The heap version is worth writing first, because it’s the honest first instinct and a fine answer on its own. Keep a min-heap of size k ordered by frequency; whenever it overflows, evict the least frequent element so only the top k survive:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

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

        // min-heap keyed by frequency: the smallest count sits on top
        PriorityQueue<Integer> heap =
            new PriorityQueue<>((a, b) -> count.get(a) - count.get(b));
        for (int key : count.keySet()) {
            heap.offer(key);
            if (heap.size() > k) heap.poll();  // drop the least frequent so far
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) result[i] = heap.poll();
        return result;
    }
}

That’s $O(n \log k)$ — already under $O(n \log n)$ since k is at most the number of distinct values. But the bucket approach shaves off the log entirely:

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

@SuppressWarnings("unchecked")
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) {
        count.put(n, count.getOrDefault(n, 0) + 1);
    }

    // bucket[f] = all values that appear exactly f times.
    // A value can appear at most nums.length times, so 0..n covers every case.
    List<Integer>[] bucket = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        int freq = e.getValue();
        if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
        bucket[freq].add(e.getKey());
    }

    // read from the highest frequency down until we've collected k values
    int[] result = new int[k];
    int idx = 0;
    for (int f = bucket.length - 1; f >= 1 && idx < k; f--) {
        if (bucket[f] == null) continue;
        for (int val : bucket[f]) {
            result[idx++] = val;
            if (idx == k) break;
        }
    }
    return result;
}

Complexity

Approach	Time	Space
Min-heap	$O(n \log k)$	$O(n)$
Bucket sort	$O(n)$	$O(n)$

Both hold up to n distinct entries, so space is $O(n)$ either way. The bucket version wins on time by refusing to sort at all.

In an interview

Lead with the heap — it shows you know how to hold onto the top k without keeping everything ordered — then name the follow-up out loud: “the counts are bounded by n, so I can bucket by frequency and skip the sort for $O(n)$.” That one observation is usually what the problem is really testing.

The trap is the buckets’ size: index them by frequency (1..n), not by the values themselves, which can be negative and blow past the array bounds. It’s easy to conflate “the number” with “how many times it appears” when you’re moving fast. The hash-map-first move here is the same one behind Valid Anagram and Group Anagrams; the whole family lives in the arrays and hashing pattern.

References

• LeetCode 347 — Top K Frequent Elements