Top K Frequent Elements

medium
Heap / Priority QueueArrayHash TableHeap / Priority QueueSorting

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

It is guaranteed that the answer is unique.

Examples

Example 1

  • Input: nums = [1,1,1,2,2,3], k = 2
  • Output: [1,2]
  • Explanation: The two most frequent elements are 1 (appears 3 times) and 2 (appears 2 times).

Example 2

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sorting by Frequency

Intuition

Count the frequency of each element using a hash map, then sort the unique elements by their frequency in descending order. The first k elements after sorting are the answer. This is a direct approach that leverages sorting to identify the top k elements.

Algorithm

  1. Build a frequency map counting how many times each element appears.
  2. Collect the unique elements and sort them by frequency in descending order.
  3. Return the first k elements from the sorted list.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }

        vector<pair<int, int>> freqList;
        for (auto& [num, count] : freq) {
            freqList.push_back({count, num});
        }

        sort(freqList.rbegin(), freqList.rend());

        vector<int> result;
        for (int i = 0; i < k; i++) {
            result.push_back(freqList[i].second);
        }
        return result;
    }
};
Java 21
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freq.entrySet());
        entries.sort((a, b) -> b.getValue() - a.getValue());

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = entries.get(i).getKey();
        }
        return result;
    }
}
Python 3.12
def topKFrequent(nums: list[int], k: int) -> list[int]:
    from collections import Counter
    freq = Counter(nums)
    sorted_items = sorted(freq.keys(), key=lambda x: freq[x], reverse=True)
    return sorted_items[:k]
Go 1.26
import "sort"

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    type pair struct {
        num, count int
    }
    pairs := make([]pair, 0, len(freq))
    for num, count := range freq {
        pairs = append(pairs, pair{num, count})
    }

    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i].count > pairs[j].count
    })

    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = pairs[i].num
    }
    return result
}
Approach 2

Min Heap

Intuition

Use a min heap (priority queue) of size k to efficiently track the top k frequent elements. First count frequencies with a hash map, then iterate through the map. Maintain a min heap of size k: push each element's frequency, and if the heap exceeds size k, remove the smallest. After processing all elements, the heap contains exactly the k most frequent elements.

Algorithm

  1. Build a frequency map counting occurrences of each element.
  2. Create a min heap ordered by frequency.
  3. For each unique element, push it onto the heap. If the heap size exceeds k, pop the element with the smallest frequency.
  4. Extract all elements from the heap into the result.
TimeO(n log k)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }

        // Min heap: {frequency, number}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;

        for (auto& [num, count] : freq) {
            minHeap.push({count, num});
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }
        return result;
    }
};
Java 21
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            minHeap.offer(new int[] { entry.getKey(), entry.getValue() });
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll()[0];
        }
        return result;
    }
}
Python 3.12
import heapq
from collections import Counter


def topKFrequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    return heapq.nlargest(k, freq.keys(), key=freq.get)
Go 1.26
import "container/heap"

type FreqItem struct {
    num, count int
}

type MinHeap []FreqItem

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool   { return h[i].count < h[j].count }
func (h MinHeap) Swap(i, j int)        { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{})  { *h = append(*h, x.(FreqItem)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    h := &MinHeap{}
    heap.Init(h)

    for num, count := range freq {
        heap.Push(h, FreqItem{num, count})
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = heap.Pop(h).(FreqItem).num
    }
    return result
}
Approach 3

Bucket Sort

Intuition

Since frequencies range from 1 to n (the array length), we can use bucket sort. Create an array of buckets where index i holds all elements that appear exactly i times. Then iterate from the highest bucket downward, collecting elements until we have k. This avoids comparison-based sorting entirely and runs in linear time.

Algorithm

  1. Build a frequency map counting occurrences of each element.
  2. Create an array of n+1 buckets, where bucket[i] stores elements with frequency i.
  3. Place each element into the bucket corresponding to its frequency.
  4. Iterate from the highest bucket (index n) down to 1, collecting elements into the result.
  5. Stop once the result contains k elements and return it.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }

        int n = nums.size();
        vector<vector<int>> buckets(n + 1);
        for (auto& [num, count] : freq) {
            buckets[count].push_back(num);
        }

        vector<int> result;
        for (int i = n; i >= 1 && result.size() < k; i--) {
            for (int num : buckets[i]) {
                result.push_back(num);
                if (result.size() == k) break;
            }
        }
        return result;
    }
};
Java 21
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] buckets = new List[nums.length + 1];
        for (int i = 0; i <= nums.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            buckets[entry.getValue()].add(entry.getKey());
        }

        int[] result = new int[k];
        int idx = 0;
        for (int i = nums.length; i >= 1 && idx < k; i--) {
            for (int num : buckets[i]) {
                result[idx++] = num;
                if (idx == k) break;
            }
        }
        return result;
    }
}
Python 3.12
from collections import Counter


def topKFrequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    n = len(nums)
    buckets = [[] for _ in range(n + 1)]

    for num, count in freq.items():
        buckets[count].append(num)

    result = []
    for i in range(n, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result
Go 1.26
func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }

    n := len(nums)
    buckets := make([][]int, n+1)
    for num, count := range freq {
        buckets[count] = append(buckets[count], num)
    }

    result := make([]int, 0, k)
    for i := n; i >= 1 && len(result) < k; i-- {
        for _, num := range buckets[i] {
            result = append(result, num)
            if len(result) == k {
                return result
            }
        }
    }
    return result
}

Frequently asked questions

What is the optimal time complexity of Top K Frequent Elements?

The most efficient approach in this guide ("Bucket Sort") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Top K Frequent Elements use?

Top K Frequent Elements is a medium-level Heap / Priority Queue problem involving Array, Hash Table, Heap / Priority Queue. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Top K Frequent Elements be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[1,1,1,2,2,3]
k=
2
Expected Output
[1,2]