Top K Frequent Elements

Master this topic with zero to advance depth.

Top K Frequent Elements

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

Visual Representation

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

Frequency Map: {1: 3, 2: 2, 3: 1}

Buckets (Count -> Elements):
1: [3]
2: [2]
3: [1]

Collect from largest count: [1, 2]

Medium

Examples

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 appears 3 times, 2 appears 2 times. The top 2 most frequent elements are [1, 2].

Input: nums = [1], k = 1
Output: [1]
1 is the only element, so it's the most frequent.

Approach 1

Level I: Brute Force (Sorting Map)

Intuition

Count the frequency of each element using a Hash Map. Convert the map entries into a list and sort the list based on frequencies in descending order. Finally, extract the first k elements.

⏱ O(N log N) dominated by sorting the map entries.💾 O(N) to store frequencies in the Hash Map.

Detailed Dry Run

Element	Frequency	Sorted Rank
1	3	1
2	2	2
3	1	3

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((a, b) -> map.get(b) - map.get(a));
        
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = list.get(i);
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

Approach 2

Level II: Better Solution (Min-Heap)

Intuition

Maintain a Min-Heap of size k. If we find an element with a higher frequency than the heap's smallest (root), we replace it. This ensures that after processing all elements, the heap contains the k most frequent ones.

⏱ O(N log K) as heap operations take $O(\log K)$ for each map entry.💾 O(N) to store frequencies in the map.

Detailed Dry Run

Heap Evolution (k=2)

Step	Element (Freq)	Heap State	Action
1	1 (3)	[(1,3)]	Push
2	2 (2)	[(2,2), (1,3)]	Push
3	3 (1)	[(3,1), (1,3), (2,2)]	Push & Pop Root (3,1)

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (int n : map.keySet()) {
            heap.add(n);
            if (heap.size() > k) heap.poll();
        }
        
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = heap.poll();
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

Approach 3

Level III: Optimal Solution (Bucket Sort)

Intuition

Frequencies range from 0 to N (length of array). We can create an array of buckets where buckets[i] contains all numbers that appear i times. By iterating through buckets from N down to 0, we can collect the top k elements in linear time.

⏱ O(N) to count frequencies and populate buckets.💾 O(N) for map and buckets.

Detailed Dry Run

Bucket Sort Visual

nums = [1,1,1,2,2,3], k = 2 Freq Map: {1:3, 2:2, 3:1}

Freq (Bucket Index)	Numbers
3	[1]
2	[2]
1	[3]

Collection (Right to Left):

Freq 3: Add 1 -> res = [1]
Freq 2: Add 2 -> res = [1, 2]
len(res) == k, STOP.

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int n : map.keySet()) {
            int freq = map.get(n);
            if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
            bucket[freq].add(n);
        }
        
        int[] res = new int[k];
        int count = 0;
        for (int i = bucket.length - 1; i >= 0 && count < k; i--) {
            if (bucket[i] != null) {
                for (int n : bucket[i]) {
                    res[count++] = n;
                    if (count == k) return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

← Previous QuestionProduct of Array Except Self

Next Question →Subarray Sum Equals K

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.