5.Top K Frequent Elements

MediumBlind 75Arrays & Hashing · 5/9

Problem

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

The test data guarantees the answer is unique: there is never a tie at the boundary between the k-th and (k+1)-th most frequent values.

Examples

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Explanation: 1 appears 3 times, 2 appears 2 times, 3 appears once.

Input:  nums = [1], k = 1
Output: [1]

Input:  nums = [4, 4, 5, 5, 5, 6], k = 1
Output: [5]

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, number of unique elements].
The answer is guaranteed to be unique.
Follow-up: do better than O(n log n).

💡 Key Insight

First count frequencies with a HashMap. The question then becomes "pick the k keys with the largest counts". Sorting all keys is O(n log n); a min-heap of size k is O(n log k). But a frequency can never exceed n, so we can use bucket sort: an array where bucket[f] lists the numbers occurring exactly f times, then read buckets from high to low — O(n) total.

Sort by Frequency

TimeO(n log n)SpaceO(n)

Intuition

Count each value, put the distinct values in a list, sort that list by count descending, and take the first k.

Algorithm

Build count: value → frequency.
Copy the keys into a list and sort by count.get(x) descending.
Return the first k entries.

Visualization

nums = [1,1,1,2,2,3]
count = {1:3, 2:2, 3:1}
sorted by count desc: [1(3), 2(2), 3(1)]
take k=2 → [1, 2]

Code

java

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.merge(num, 1, Integer::sum);
        }
        List<Integer> keys = new ArrayList<>(count.keySet());
        // Highest frequency first
        keys.sort((a, b) -> Integer.compare(count.get(b), count.get(a)));
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = keys.get(i);
        }
        return result;
    }
}

Complexity

Time: O(n log n) — counting is O(n); sorting up to n distinct keys is O(n log n).
Space: O(n) — the map and key list.

Min-Heap of Size k

TimeO(n log k)SpaceO(n + k)

Intuition

We only care about the top k, so we do not need everything sorted. Keep a min-heap of at most k values ordered by frequency. Whenever it grows past k, evict the root — the least frequent of the candidates. What remains is exactly the k most frequent.

Algorithm

Build count.
Create a PriorityQueue<Integer> ordered by count.get(x) ascending.
For each distinct value: offer it; if heap.size() > k, poll.
Pop the heap into the result array.

Visualization

count = {1:3, 2:2, 3:1}, k = 2

offer 1 → heap [1(3)]
offer 2 → heap [2(2), 1(3)]
offer 3 → heap [3(1), 1(3), 2(2)] size 3 > 2 → poll 3
result → [2, 1]

Code

java

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 num : nums) {
            count.merge(num, 1, Integer::sum);
        }
        // Min-heap by frequency: the root is the weakest candidate
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(count.get(a), count.get(b)));
        for (int num : count.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll(); // drop the least frequent
            }
        }
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = heap.poll();
        }
        return result;
    }
}

Complexity

Time: O(n log k) — each of up to n distinct values costs O(log k) heap work.
Space: O(n + k) — the map plus the heap.

Bucket SortOptimal

TimeO(n)SpaceO(n)

Intuition

Frequencies are integers between 1 and n. Create n + 1 buckets where bucket[f] holds every value that appears exactly f times. Scanning buckets from n down to 1 visits values in descending frequency without any comparison sort — stop as soon as k values are collected.

Algorithm

Build count.
Create List<Integer>[] bucket = new List[n + 1].
For each (value, freq), append value to bucket[freq].
For f from n down to 1, take values from bucket[f] until k are collected.

Dry Run

flowchart TD
    A["nums = [1,1,1,2,2,3]"] --> B["count = {1:3, 2:2, 3:1}"]
    B --> C["bucket[3] = [1]<br/>bucket[2] = [2]<br/>bucket[1] = [3]"]
    C --> D["scan f = 6..1"]
    D --> E["f=3: take 1"]
    E --> F["f=2: take 2"]
    F --> G["collected k=2: return [1, 2]"]

Code

java

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.merge(num, 1, Integer::sum);
        }
        // bucket[f] = values that appear exactly f times (f is at most n)
        List<List<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            bucket.add(new ArrayList<>());
        }
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            bucket.get(e.getValue()).add(e.getKey());
        }
        int[] result = new int[k];
        int idx = 0;
        for (int f = nums.length; f >= 1 && idx < k; f--) {
            for (int num : bucket.get(f)) {
                result[idx++] = num;
                if (idx == k) {
                    break;
                }
            }
        }
        return result;
    }
}

Complexity

Time: O(n) — counting, filling buckets and scanning n + 1 buckets are all linear.
Space: O(n) — the map and the buckets.

Complexity Comparison

Approach	Time	Space
Sort by Frequency	O(n log n)	O(n)
Min-Heap of Size k	O(n log k)	O(n + k)
Bucket Sort	O(n)	O(n)

Common Pitfalls

Using a max-heap of all elements and popping k times works but is O(n log n) to build via repeated offers — the size-k min-heap is the intended heap solution.
Sizing buckets as n instead of n + 1 — when every element is the same value, its frequency is n and bucket[n] must exist.
Writing a - b in comparators can overflow in general; Integer.compare is safe.
Iterating over nums (with duplicates) instead of count.keySet() when filling the heap or buckets inserts the same value multiple times.