Top K Frequent Elements

Problem

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

Examples

Example 1:

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

Example 2:

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

Constraints

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

Follow up

In case of a tie, i.e. if 2 numbers have same frequency, then the larger number should be given preference.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/MfQ9PHKyuMo" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Sorting

We can create a map of number and frequency. Sort the map based on frequency and return first k elements. But the time complexity will be O(n log n). But of course we can do better.

Complexity

• ⏰ Time complexity: O(n + m log m + k), where n is the size of nums and m is number of unique elements. Because first we build frequency map - O(n), then we sort the elements - O(m log m) and then pick k elements. In the worst case, all the elements are unique, hence m = n.
• 🧺 Space complexity: O(n)

Method 2 - Using Max Heap

Intuition

To avoid a full sort, we can use a data structure to help us find the "top" elements. A Max-Heap is a natural first thought, as it always keeps the element with the highest value (frequency) at the top.

Approach

1. Build the frequency map as before.
2. Insert all M unique number-frequency pairs into a Max-Heap.
3. Call "pop" on the heap k times to extract the k elements with the highest frequencies.

Complexity

• ⏰ Time complexity: O(n + m + k log m).
  • Building frequency map - O(n)
  • Buidling max heap - O(m) if build in one go, otherwise O(m log m)
  • Take k elements - O(k log m)
• 🧺 Space complexity: O(n)

Method 3 - Using HashMap and Min Heap 🥈

Intuition

The inefficiency of the Max-Heap was that it held all M elements. The key optimization is to realize we only need to maintain a collection of k elements at any time. A Min-Heap of size k is perfect for this. It keeps the "worst" of the top k candidates seen so far at the top, ready to be ejected if a better candidate comes along.

Approach

1. Build the frequency map.
2. Iterate through the number-frequency pairs.
3. For each pair, push it onto the Min-Heap.
4. If the heap's size grows larger than k, pop the smallest element (the one with the lowest frequency).

Code

Java

class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        if (k == nums.length) {
            return nums;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int n : nums) {
            counts.put(n, counts.getOrDefault(n, 0) + 1);
        }

        Queue<Integer> heap = new PriorityQueue<>((a, b) -> counts.get(a) - counts.get(b));

        for (int n : counts.keySet()) {
            heap.add(n);
            if (heap.size() > k) {
                heap.poll();
            }
        }

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

Python - Builtin

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        if k == len(nums):
            return nums

        counts = collections.Counter(nums)

        return heapq.nlargest(k, counts.keys(), key=counts.get)

Python - detailed

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        if k == len(nums):
            return nums   
     
        counts = collections.Counter(nums)
        
        min_heap = []
        for num, freq in counts.items():
            heapq.heappush(min_heap, (freq, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)

        return [num for freq, num in min_heap]

Complexity

• ⏰ Time complexity: O(n log k), where n is the size of nums and k is size of min heap.
  • Count the frequency of elements in O(n) using a hashmap.
  • O(n log k) for using min heap
  • O(n + k) using bucket sort.
• 🧺 Space complexity: O(n), for the hashmap and additional data structures.

Method 4 - Bucket Sort 🏆

Intuition

We can use array of linked list, where we can bucketize the numbers based on there frequency. The bucket index will be frequency, values will be number added to that bucket. Number of buckets will be = n + 1. Why? Because what if all the element occur once, then it is n; Also, 0 for 0 frequency case. This helps in avoiding edge cases, where we need to sometimes do index-1 etc.

Approach

1. Build the frequency map.
2. Create an array of lists (the "buckets"), of size N+1. The index of this array represents a frequency.
3. Iterate through the frequency map. For each number, add it to the list at the bucket index corresponding to its frequency. (e.g., a number appearing 3 times goes into buckets[3]).
4. Iterate through the buckets array backwards, starting from the highest possible frequency (N). Collect the numbers from the buckets until you have k elements.
5. Return the collected elements. This approach has a linear O(N) time complexity.

Code

Java

class Solution {

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

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

        for (int num : counts.keySet()) {
            buckets[counts.get(num)].add(num);
        }

        List<Integer> ansList = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && ansList.size() < k; i--) {
            if (!buckets[i].isEmpty()) {
                ansList.addAll(buckets[i]);
            }
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

Python

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = collections.Counter(nums)
        n = len(nums)
        buckets = [[] for _ in range(n + 1)]

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

        ans = []
        for i in range(n, -1, -1):
            if buckets[i]:
                ans.extend(buckets[i])
            if len(ans) >= k:
                break

        return ans[:k]

Complexity

• ⏰ Time complexity: O(n) each to count frequencies, populate the bucket and collect the top k frequent elements.
• 🧺 Space complexity: O(n) for the frequency map and bucket.

Follow-up Solution (Tie-breaker: Larger Number First)

If two elements have the same frequency, return the larger element first. This affects both sorting and heap approaches.

Method 1 - Sorting

Sort by frequency descending, then by value descending.

Code

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        # Sort by frequency descending, then value descending
        pairs = sorted(freq.items(), key=lambda x: (x[1], x[0]), reverse=True)
        return [num for num, _ in pairs[:k]]

Method 2 - Using hashmap and minheap

Use (-frequency, -number) as the key so that higher frequency and, for ties, larger numbers come first.

Code

Java

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
        // Min-heap: first by frequency, then by value (larger first)
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0]; // frequency ascending
            return b[1] - a[1]; // value descending
        });
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.add(new int[]{entry.getValue(), entry.getKey()});
            if (heap.size() > k) heap.poll();
        }
        List<Integer> ans = new ArrayList<>();
        while (!heap.isEmpty()) ans.add(heap.poll()[1]);
        Collections.reverse(ans); // To get highest frequency/largest first
        return ans;
    }
}

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        # Use (-freq, -num) so higher freq and larger num come first
        heap = [(-count, -num) for num, count in freq.items()]
        heapq.heapify(heap)
        ans = []
        for _ in range(k):
            count, num = heapq.heappop(heap)
            ans.append(-num)
        return ans