Top K Frequent Elements

Problem Description

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

Examples

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴
• k is in the range [1, number of unique elements in nums]
• The answer is guaranteed to be unique.

Sorting by Frequency Is Slower Than It Needs to Be

Count frequencies, then sort by frequency descending, take the top k. That’s the obvious path, and it’s O(n log n). But the problem only asks for the k most frequent, not a fully sorted ranking. When you only need a partial order, you have two faster options: a heap of size k, or bucket sort by frequency. Bucket sort gives O(n) and is the answer the problem is nudging you toward with the constraint k <= number of unique elements.

Solution 1: Sort by Frequency

Count with a hash map, sort descending by count, return the first k keys.

import java.util.*;

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);

        return count.entrySet().stream()
            .sorted((a, b) -> b.getValue() - a.getValue())
            .limit(k)
            .mapToInt(Map.Entry::getKey)
            .toArray();
    }
}

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        # most_common(k) returns pairs sorted by frequency descending
        return [num for num, _ in count.most_common(k)]

#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> count;
        for (int num : nums) count[num]++;

        std::vector<std::pair<int,int>> freq(count.begin(), count.end());
        std::sort(freq.begin(), freq.end(), [](auto& a, auto& b) {
            return b.second < a.second;
        });

        std::vector<int> result;
        for (int i = 0; i < k; i++) result.push_back(freq[i].first);
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). Counting is O(n), sorting the unique elements is O(u log u) where u <= n.
• Space Complexity: O(n). The frequency map.

Where it breaks: the problem guarantees a unique answer, which means this sort is stable enough. But the interviewer will likely ask if you can do better. This signals you haven’t finished thinking.

Solution 2: Bucket Sort by Frequency

The maximum possible frequency is n (all elements are the same). Create n + 1 buckets where bucket[i] holds all numbers that appear exactly i times. Walk backward from the highest bucket collecting elements until you have k.

import java.util.*;

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);

        // index i = frequency, value = list of numbers with that frequency
        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[] result = new int[k];
        int idx = 0;
        for (int freq = nums.length; freq >= 1 && idx < k; freq--) {
            for (int num : buckets.get(freq)) {
                result[idx++] = num;
                if (idx == k) return result;
            }
        }
        return result;
    }
}

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)

        # index i = frequency, value = list of numbers with that frequency
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            buckets[freq].append(num)

        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> count;
        for (int num : nums) count[num]++;

        // index i = frequency, value = numbers with that frequency
        std::vector<std::vector<int>> buckets(nums.size() + 1);
        for (auto& [num, freq] : count) buckets[freq].push_back(num);

        std::vector<int> result;
        for (int freq = nums.size(); freq >= 1 && (int)result.size() < k; freq--) {
            for (int num : buckets[freq]) {
                result.push_back(num);
                if ((int)result.size() == k) return result;
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Counting is O(n), building buckets is O(n), collecting results is O(n).
• Space Complexity: O(n). Both the count map and bucket array scale with input size.

Where it breaks: the bucket array size is n + 1. For very sparse inputs (many unique elements), this wastes space. A heap of size k would use O(k) space instead, which is better when k is small and n is large.

Why Not a Min-Heap of Size K?

A min-heap approach works and gives O(n log k) time, O(k) space. It’s strictly better than sorting and arguably more interview-friendly since it’s a common “top k” pattern. The bucket sort beats it on time (O(n) vs O(n log k)) but uses more space. Both are valid answers; know which trade-off you’re making.

Common Mistakes

• Off-by-one on bucket size. The bucket array needs n + 1 slots (indices 0 through n), because a single element can appear n times. n slots would miss the highest-frequency bucket.
• Using a max-heap of size n instead of a min-heap of size k. Heapifying all n elements then popping k times is O(n + k log n), which doesn’t beat O(n log n) sorting by much. Keep the heap bounded to size k.
• Returning counts instead of elements. The problem asks for the elements themselves, not their frequencies.

Frequently Asked Questions

What if k equals the number of unique elements? Then every unique element is in the answer. Both approaches still work correctly; the bucket sort simply walks all non-empty buckets.

How does Python’s Counter.most_common(k) work internally? For small k, it uses heapq.nlargest, which is O(n log k). For k equal to the full list size, it falls back to a full sort. In interviews, it’s worth knowing this detail if you use it.

Can this be solved in O(n) guaranteed worst case? The bucket sort is O(n) average and worst case since hash map operations are O(1) amortized. The heap approach is O(n log k) worst case. For guaranteed O(n), bucket sort is the answer.

← All Problems