Problem 4.5 · HashingMedium

Top K Frequent Elements

PatternFrequency Counting Top K with a Heap

What it teaches: Count first, then select: bucket sort by frequency gives O(n), beating a full sort.

Practise it on judges as “Top K Frequent Elements”.

The problem

Given an integer array nums and an integer k, return the k most frequent elements, in any order. The answer is guaranteed to be unique.

Example 1

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

Example 2

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

Constraints

1 ≤ nums.length ≤ 10⁵
k is between 1 and the number of distinct values
Must beat O(n log n)

Pattern clues in the wording

→ "K most frequent": count, then pick the top k
→ Frequencies are bounded by n, so they can index an array

These clues point to Frequency Counting: Count how many times each value appears (with an int[26] or a HashMap), then answer from the counts.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        return new int[k];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,1,1,2,2,3] k = 2	[1,2]
2	nums = [1] k = 1	[1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Count, then min-heap of size k · O(n log k)2. Optimal: bucket sort by frequency · O(n)

Count, then min-heap of size k

Time O(n log k) Space O(n)

Count frequencies. Push each distinct value into a min-heap ordered by count; if the heap grows past k, remove the least frequent. The heap ends with the k most frequent.

Approach 1

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(count.get(a), count.get(b)));
        for (int v : count.keySet()) {
            heap.offer(v);
            if (heap.size() > k) heap.poll();
        }
        int[] out = new int[k];
        for (int i = 0; i < k; i++) out[i] = heap.poll();
        return out;
    }
}

Verdict: Good when k is small; the Heaps module covers this Top-K pattern in depth.

Optimal: bucket sort by frequency

Time O(n) Space O(n)

A value can appear at most n times. Create n + 1 buckets; put each distinct value into the bucket for its count. Then walk buckets from n down to 1, collecting values until you have k.

▶ Dry run: Buckets indexed by frequencynums = [1, 1, 1, 2, 2, 3], k = 2

count(map)

1: 32: 23: 1

Step 1/4Count each value.

Approach 2

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : count.entrySet()) buckets.get(e.getValue()).add(e.getKey());
        int[] out = new int[k];
        int idx = 0;
        for (int f = nums.length; f >= 1 && idx < k; f--) {
            for (int v : buckets.get(f)) {
                if (idx == k) break;
                out[idx++] = v;
            }
        }
        return out;
    }
}

Verdict: Linear: counting is O(n) and the buckets have n + 1 slots.

Before you submit

Edge cases and common mistakes

Test these inputs

k equals the number of distinct values
All values the same
Negative values

Mistakes people make

Using a max-heap of all values (O(n log n)) when a size-k min-heap suffices.
Indexing buckets by value instead of frequency.

Interview

Follow-up questions

What if the data is a stream and k is small?

Command Palette