Top K Frequent Elements | Leetcode 347

Welcome to our deep dive on Top K Frequent Elements (Leetcode 347). This is a phenomenal problem to test your knowledge of Heaps (Priority Queues) and HashMaps working together.

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.

Example: nums = [1,1,1,2,2,3], k = 2 => Output: [1,2] (Explanation: 1 appears 3 times, 2 appears two times. They are the top 2.)

Approach: HashMap + Min-Heap O(N log K)

The most mathematically optimal and standard way to track the "top K" of anything is by using a Min-Heap.

1. First, we must iterate through the entire original array nums to count the exact frequency of every unique element. We store this in a HashMap mapping Value -> Frequency.
2. Keep a Min-Heap data structure that will aggressively store arrays/objects in the format (Frequency, Value). It automatically sorts itself placing the smallest frequency strictly at the root top!
3. Iterate cleanly through the keys in our HashMap. Push each element into our structured Min-Heap.
4. If the physical size of our Min-Heap exceeds k at any point, we violently pop the element from it. Because it is a Min-Heap, popping mathematically removes the element with the absolute smallest frequency!
5. After iterating perfectly through all elements, what remains trapped securely in the heap? Exactly the k elements with the strictly largest frequencies.

import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(N) cleanly count optimally
        freq_map = Counter(nums)
        
        min_heap = []
        
        for num, freq in freq_map.items():
            heapq.heappush(min_heap, (freq, num))
            
            # Maintain heap size securely at K
            if len(min_heap) > k:
                heapq.heappop(min_heap)
                
        # Extract the results comfortably perfectly neatly cleanly purely
        return [num for (freq, num) in min_heap]

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (347)