Top K Frequent Elements (LC 347)

Pattern: Heap / Bucket Sort by Frequency
Difficulty: Medium
Key Concept: Count frequencies, then either use a min-heap of size k on frequencies or bucket indices by frequency for O(n) time.

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Input: nums, k (guaranteed valid).
Output: int[] length k.

Example

nums = [1,1,1,2,2,3], k = 2 → [1,2] (1 appears 3 times, 2 appears 2 times).

---

1. Algorithm & Pseudocode

Brute force

1. Count frequencies O(n).
2. Sort unique entries by frequency descending — O(u log u) where u = unique count ≤ n.
3. Take first k.

Pseudocode

freq = count(nums)
entries = list of (value, count)
sort entries by count desc
return first k values

Optimal A — Min-heap of size k

1. Build frequency map.
2. Keep PriorityQueue of k (count, value) using min-heap by count — if size > k, evict smallest count.
3. Extract values — O(n log k) time, O(u + k) space.

Optimal B — Bucket sort by frequency

1. Frequency map.
2. List<Integer>[] buckets of size n+1 — index = frequency; append values that occur that many times.
3. Scan buckets from high index down until k collected — O(n) time, O(n) space.

Pseudocode (bucket)

freq map
bucket[f] = list of nums with frequency f
for f from n down to 1:
    add all in bucket[f] to answer until size k

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Min-heap of k tracks the k largest frequencies seen so far; evicting the smallest among them keeps only top candidates.
• Bucket exploits that maximum frequency ≤ n (array length), so frequency is a bounded index.
• Why not max-heap of all unique: That heap has u elements — O(n log u) pops; min-heap k is better when k ≪ u.

---

3. The Dry Run

nums = [1,1,1,2,2,3], k = 2

Frequencies: 1→3, 2→2, 3→1

Bucket (index = frequency)

freq index	values stored
0	(unused)
1	[3]
2	[2]
3	[1]

Scan from f=3: take 1 → ans [1]
f=2: take 2 → ans [1,2] → stop (k=2)

ASCII

freq:  1:###  2:##  3:#

bucket[3] = [1]
bucket[2] = [2]
bucket[1] = [3]
         ↑ collect from top down

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    // Time: O(n + u log u), Space: O(u)
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freq.entrySet());
        entries.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = entries.get(i).getKey();
        return ans;
    }
}

Optimal (min-heap k)

import java.util.*;

class Solution {
    // Time: O(n + u log k), Space: O(u + k)
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        for (var e : freq.entrySet()) {
            pq.offer(new int[] { e.getKey(), e.getValue() });
            if (pq.size() > k) pq.poll();
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = pq.poll()[0];
        return ans;
    }
}

Optimal (bucket O(n))

import java.util.*;

class SolutionBucket {
    // Time: O(n), Space: O(n)
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        List<Integer>[] buckets = new List[nums.length + 1];
        for (var e : freq.entrySet()) {
            int f = e.getValue();
            if (buckets[f] == null) buckets[f] = new ArrayList<>();
            buckets[f].add(e.getKey());
        }
        int[] ans = new int[k];
        int t = 0;
        for (int f = nums.length; f >= 0 && t < k; f--) {
            if (buckets[f] == null) continue;
            for (int v : buckets[f]) {
                ans[t++] = v;
                if (t == k) break;
            }
        }
        return ans;
    }
}

---

5. The “Java vs. Others” Edge

• Map.merge(x, 1, Integer::sum) is idiomatic frequency counting.
• PriorityQueue<int[]> avoids boxing pairs; Comparator.comparingInt(a -> a[1]) compares frequency.
• Generic array List<Integer>[] triggers unchecked warning — acceptable on LeetCode; use @SuppressWarnings in production if needed.
• var (Java 10+) shortens entry loops.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute sort by freq	O(n + u log u)	O(u)	u = unique elements
Min-heap size k	O(n + u log k)	O(u + k)	Good when k ≪ u
Bucket by frequency	O(n)	O(n)	Uses freq bound ≤ n