Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Top K Frequent Elements

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 Count Buckets: 0: [] 1: [3] (val 3 appears 1 time) 2: [2] (val 2 appears 2 times) 3: [1] (val 1 appears 3 times) 4: [] 5: [] 6: [] Iterate buckets from right to left: Bucket 3 -> [1] Bucket 2 -> [2] Result (k=2): [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, 3 appears 1 time. Top 2 are [1, 2].

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

Level I: Sorting (Naive)

Intuition

Count the frequency of each element and then sort the elements based on their count in descending order. Pick the first k elements.

Thought Process

  1. Use a Hash Map to count occurrences.
  2. Create a list of pairs (element, frequency).
  3. Sort the list by frequency in descending order.
  4. Take the top k elements.
⏱ O(N log N) for sorting💾 O(N) to store frequencies

Detailed Dry Run

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

  1. Map: {1: 2, 2: 1}
  2. Pairs: [(1, 2), (2, 1)]
  3. Sorted: [(1, 2), (2, 1)]
  4. result: [1]
java
import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

        List<Integer> list = new ArrayList<>(count.keySet());
        list.sort((a, b) -> count.get(b) - count.get(a));

        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = list.get(i);
        return res;
    }
}
Approach 2

Level II: Bucket Sort (Optimal)

Intuition

Since frequency is bounded by array length NN, we can use buckets where bucket[i] stores elements that appear ii times. Iterate from NN down to 1.

Thought Process

  1. Count frequencies with a Map.
  2. Create an array of lists buckets of size N+1N+1.
  3. Place each element in its corresponding frequency bucket.
  4. Traverse buckets from right to left to collect top kk elements.
⏱ O(N)💾 O(N)

Detailed Dry Run

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

  1. Map: {1:3, 2:2, 3:1}
  2. Buckets: [[], [3], [2], [1], [], [], []]
  3. Bucket 3: adds [1]. Result [1]
  4. Bucket 2: adds [2]. Result [1, 2]. Done.
java
import java.util.*;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : count.keySet()) {
            int freq = count.get(key);
            if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
            buckets[freq].add(key);
        }
        int[] res = new int[k];
        int idx = 0;
        for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
            if (buckets[i] != null) {
                for (int n : buckets[i]) {
                    res[idx++] = n;
                    if (idx == k) return res;
                }
            }
        }
        return res;
    }
}
Approach 3

Level III: Min-Heap (Optimal)

Intuition

Instead of sorting all elements, we can maintain a Min-Heap of size k. If the size exceeds k, we pop the element with the smallest frequency. At the end, the heap contains the k most frequent elements.

Thought Process

  1. Count frequencies using a Map.
  2. Iterate through unique elements and push them into a Min-Heap based on frequency.
  3. If heap size > k, pop from heap.
  4. The remaining elements in the heap are the result.
⏱ O(N log K)💾 O(N) for frequency map

Detailed Dry Run

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

  1. Map: {1:3, 2:2, 3:1}
  2. Push 1 (freq 3): Heap [(1,3)]
  3. Push 2 (freq 2): Heap [(2,2), (1,3)]
  4. Push 3 (freq 1): Heap [(3,1), (2,2), (1,3)] -> Size 3 > k, Pop (3,1). Final Heap: [(2,2), (1,3)] -> Result [1, 2]
java
import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> count.get(a) - count.get(b));
        for (int n : count.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) {
        System.out.println(Arrays.toString(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }
}
← Previous QuestionHouse Robber III
Next Question →Kth Largest Element in an Array