Top K Frequent Elements

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.

What to notice first

Frequency counting with a hash map is always the first step. The question is just how efficiently you find the top-k after that.

Examples

Input	k	Output
[1,1,1,2,2,3]	2	[1,2]
[1]	1	[1]

Constraints

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

Real-World Applications

Where this pattern appears

• Analytics dashboards — show the top-k most visited pages from a hit-count log
• Autocomplete engines — suggest the k most frequently typed queries
• Trending topics — surface the k hashtags with the most posts in a time window
• Recommendation systems — return k most commonly co-purchased items

Complexity Comparison

Approach	Time	Space	Best When
Max Heap	O(n log k)	O(n)	k << n, memory matters
Bucket Sort	O(n)	O(n)	Best asymptotic, when n is large

Which approach should you learn first?

• Pick Max Heap for interviews — it is the expected answer and generalises to streaming data.
• Pick Bucket Sort when you want the asymptotically optimal O(n) solution and can mention it as the follow-up.

Recommended

Max Heap

O(n log k) time · O(n) space

Interview Favourite

Bucket Sort

O(n) time · O(n) space

Approach 1: Max Heap

★ Recommended

Count element frequencies with a hash map, then push all (freq, num) pairs into a max-heap. Pop k times to get the top-k most frequent elements.

⏱ Time O(n log k) n insertions into a heap of size ≤ n 💾 Space O(n) Freq map + heap store all unique elements

Step-by-step Example

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

Step	State
Build freq map	{1:3, 2:2, 3:1}
Max-heap (by freq)	[(3,1), (2,2), (1,3)]
Pop 1	element 1 (freq 3)
Pop 2	element 2 (freq 2)
Return	[1, 2]

Animated walkthrough

How the max heap extracts the top-k most frequent elements

Use Next or Autoplay to watch frequency counting and then heap extraction.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function topKFrequent(nums, k):
    freq = count all nums
    return k largest by frequency from freq

Solution Code

Python

top_k_frequent_max_heap.py

from typing import List
from collections import Counter
import heapq

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = Counter(nums)
    # heapq.nlargest uses a heap internally — O(n log k)
    return heapq.nlargest(k, freq.keys(), key=lambda x: freq[x])

print(topKFrequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]
print(topKFrequent([1], 1))                  # [1]

C++

top_k_frequent_max_heap.cpp

#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

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

        // max-heap: (frequency, number)
        priority_queue<pair<int, int>> maxHeap;
        for (auto& [num, count] : freq) {
            maxHeap.push({count, num});
        }

        vector<int> result;
        while (k-- > 0) {
            result.push_back(maxHeap.top().second);
            maxHeap.pop();
        }
        return result;
    }
};

Java

top_k_frequent_max_heap.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) freq.merge(num, 1, Integer::sum);

        // max-heap ordered by frequency descending
        PriorityQueue<Integer> maxHeap =
            new PriorityQueue<>((a, b) -> freq.get(b) - freq.get(a));
        maxHeap.addAll(freq.keySet());

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
}

JavaScript

top_k_frequent_max_heap.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
    }
    // Sort entries by frequency descending and take first k elements
    return [...freq.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(([num]) => num);
}

Rust

top_k_frequent_max_heap.rs

use std::collections::HashMap;

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, i32> = HashMap::new();
        for num in &nums {
            *freq.entry(*num).or_insert(0) += 1;
        }

        let mut pairs: Vec<(i32, i32)> = freq.into_iter().map(|(num, cnt)| (cnt, num)).collect();
        // Sort by frequency descending
        pairs.sort_unstable_by(|a, b| b.0.cmp(&a.0));

        pairs.into_iter().take(k as usize).map(|(_, num)| num).collect()
    }
}

Go

top_k_frequent_max_heap.go

package main

import "sort"

func topKFrequent(nums []int, k int) []int {
  freq := 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 by frequency descending
  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: Bucket Sort

🎯 Interview Favourite

Since frequency is bounded by n, create n+1 buckets indexed by frequency. bucket[i] holds all numbers that appear exactly i times. Fill from the freq map, then iterate buckets from high to low, collecting elements until k are found. This achieves O(n) time.

⏱ Time O(n) Two passes — one to count, one to collect 💾 Space O(n) Freq map + bucket array both store n elements

Step-by-step Example

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

Step	State
Build freq map	{1:3, 2:2, 3:1}
n = 6, create buckets[0..6]	all empty
Fill buckets	bucket[3]=[1], bucket[2]=[2], bucket[1]=[3]
Scan from bucket[6] down	bucket[6..4] empty
bucket[3] = [1]	add 1, count=1
bucket[2] = [2]	add 2, count=2=k, done
Return	[1, 2]

Pseudocode

function topKFrequent(nums, k):
    freq = count all nums
    buckets = array of (n+1) empty lists
    for num, count in freq:
        buckets[count].append(num)
    result = []
    for i from n down to 1:
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]

Solution Code

Python

top_k_frequent_bucket_sort.py

from typing import List
from collections import Counter

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = Counter(nums)
    n = len(nums)
    buckets: List[List[int]] = [[] for _ in range(n + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    result: List[int] = []
    for i in range(n, 0, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result[:k]

print(topKFrequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]
print(topKFrequent([1], 1))                  # [1]

C++

top_k_frequent_bucket_sort.cpp

#include <unordered_map>
#include <vector>
using namespace std;

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

        int n = (int)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 && (int)result.size() < k; i--) {
            for (int num : buckets[i]) {
                result.push_back(num);
                if ((int)result.size() == k) break;
            }
        }
        return result;
    }
};

Java

top_k_frequent_bucket_sort.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> freq = new HashMap<>();
        for (int num : nums) freq.merge(num, 1, Integer::sum);

        int n = nums.length;
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = new List[n + 1];
        for (int i = 0; i <= n; i++) buckets[i] = new ArrayList<>();

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

        int[] result = new int[k];
        int idx = 0;
        for (int i = n; i >= 1 && idx < k; i--) {
            for (int num : buckets[i]) {
                result[idx++] = num;
                if (idx == k) break;
            }
        }
        return result;
    }
}

JavaScript

top_k_frequent_bucket_sort.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
    }

    const n = nums.length;
    const buckets = Array.from({ length: n + 1 }, () => []);
    for (const [num, count] of freq) {
        buckets[count].push(num);
    }

    const result = [];
    for (let i = n; i >= 1 && result.length < k; i--) {
        for (const num of buckets[i]) {
            result.push(num);
            if (result.length === k) return result;
        }
    }
    return result;
}

Rust

top_k_frequent_bucket_sort.rs

use std::collections::HashMap;

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut freq: HashMap<i32, usize> = HashMap::new();
        for num in &nums {
            *freq.entry(*num).or_insert(0) += 1;
        }

        let n = nums.len();
        let mut buckets: Vec<Vec<i32>> = vec![vec![]; n + 1];
        for (num, count) in &freq {
            buckets[*count].push(*num);
        }

        let mut result: Vec<i32> = Vec::new();
        for i in (1..=n).rev() {
            for &num in &buckets[i] {
                result.push(num);
                if result.len() == k as usize {
                    return result;
                }
            }
        }
        result
    }
}

Go

top_k_frequent_bucket_sort.go

package main

func topKFrequentBucket(nums []int, k int) []int {
  freq := 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
}

Common mistakes

• Off-by-one: create n+1 buckets (indices 0..n) — frequency n is valid when all elements are identical.
• Returning frequencies instead of elements: the answer should be the numbers themselves, not their counts.
• Not handling k equal to all unique elements: the loop must continue until exactly k elements are collected, not just until the first non-empty bucket is exhausted.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

top_k_frequent_elements_space_optimized.py

"""
Solution for Top K Frequent Elements
"""

def solve():
    """Implementation for approach 3 of Top K Frequent Elements"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

top_k_frequent_elements_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Top K Frequent Elements
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

TopKFrequentElementsSpaceOptimized.java

/**
 * Solution for Top K Frequent Elements
 * Approach 3
 */
public class TopKFrequentElementsSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

top_k_frequent_elements_space_optimized.js

/**
 * Solution for Top K Frequent Elements
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

top_k_frequent_elements_space_optimized.rs

/// Solution for Top K Frequent Elements
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

top_k_frequent_elements_space_optimized.go

package main

import "fmt"

// Solution for Top K Frequent Elements
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum ↗ Easy #1
• Group Anagrams ↗ Medium #49
• Find Median from Data Stream ↗ Hard #295

Interview Tips

Key trade-offs to discuss

• Bucket sort achieves O(n) — mention it as the optimal approach even if you code the heap first; interviewers reward knowing both.
• Key insight for bucket sort: frequency is bounded by n, so buckets have finite size — this is the crucial observation that enables O(n).
• Follow-up — what if k changes frequently? Maintain a heap live as elements stream in; bucket sort requires knowing n upfront.
• JavaScript note: Map + sort is effectively the heap approach — no native priority queue in JS, but the sort brings the same O(n log n) result.

← Previous
#322 Coin Change Next
#349 Intersection of Two Arrays →