Leetcode 347. Top K Frequent Elements

Let's understand what we're being asked to do. We have an array like [1, 1, 1, 2, 2, 3] and a value k=2, and we need to return the 2 most frequent elements.

Tracing through: count the frequencies: 1 appears 3 times, 2 appears 2 times, 3 appears 1 time. The top 2 most frequent are 1 (3 times) and 2 (2 times), so return [1, 2].

Important constraint: We need to do better than O(n log n) time complexity. A naive approach of sorting by frequency would be O(n log n), but we can achieve O(n log k) or even O(n).

Edge cases to consider: What if multiple elements have the same frequency? What if k equals the number of unique elements? What if all elements have the same frequency?

First, build a frequency map by iterating through the array and counting occurrences of each element. Then, convert the frequency map into an array of (element, frequency) pairs and sort this array by frequency in descending order. Finally, take the first k elements from the sorted array. This approach is straightforward but requires sorting all unique elements, leading to O(n log n) complexity.

def top_k_frequent(nums, k):
    """
    Find k most frequent elements using frequency map and sorting.
    Time: O(n log n), Space: O(n)
    """
    # Build frequency map
    freq_map = {}
    for num in nums:
        if num in freq_map:
            freq_map[num] += 1
        else:
            freq_map[num] = 1
    
    # Convert to list of (element, frequency) pairs
    freq_pairs = []
    for num, count in freq_map.items():
        freq_pairs.append((num, count))
    
    # Sort by frequency in descending order (brute force - sorts ALL elements)
    for i in range(len(freq_pairs)):
        for j in range(i + 1, len(freq_pairs)):
            if freq_pairs[j][1] > freq_pairs[i][1]:
                # Swap elements
                temp = freq_pairs[i]
                freq_pairs[i] = freq_pairs[j]
                freq_pairs[j] = temp
    
    # Extract first k elements
    result = []
    for i in range(k):
        result.append(freq_pairs[i][0])
    
    return result

We need to solve two sub-problems: counting frequencies (how many times each element appears) and finding the top k (extracting the k elements with highest counts).

The first part is straightforward with a frequency map. The challenge is the second part: how do we efficiently find the top k without sorting all elements?

If we sort all unique elements by frequency, that's O(n log n) where n is the array length. But we only need the top k elements, not a fully sorted list.

By maintaining only k elements at a time (using a size-k structure), we can reduce this to O(n log k). When k is much smaller than n, this is a huge improvement!

Imagine you're tracking the top 3 most popular songs from a playlist of 1 million songs. You don't need to rank all 1 million songs - you just need to keep track of your current 'top 3' and update it as you scan through.

When you encounter a new song, you only compare it against your current top 3. If it's more popular than the least popular in your top 3, swap it in. This way, you only maintain 3 songs in memory, not 1 million.

This 'keep only what you need' approach is the key insight for achieving better than O(n log n) complexity.

First, build a frequency map to count occurrences of each element. Then, use a min-heap of size k to track the k most frequent elements. Iterate through the frequency map: for each element, if the heap has fewer than k elements, add it; otherwise, if the current element's frequency is greater than the minimum frequency in the heap, remove the minimum and add the current element. This maintains only k elements at a time, achieving O(n log k) complexity. An alternative optimal approach uses bucket sort to achieve O(n) by grouping elements by frequency.

import heapq
from collections import Counter
def top_k_frequent(nums, k):
    """
    Find k most frequent elements using frequency map and min-heap.
    Time: O(n log k), Space: O(n)
    """
    # Build frequency map
    freq_map = Counter(nums)
    
    # Min-heap to track k most frequent elements
    # Heap stores tuples: (frequency, element)
    min_heap = []
    
    # Iterate through frequency map
    for num, freq in freq_map.items():
        # If heap has fewer than k elements, add current element
        if len(min_heap) < k:
            heapq.heappush(min_heap, (freq, num))
        # If current frequency > minimum frequency in heap
        elif freq > min_heap[0][0]:
            # Remove minimum and add current element
            heapq.heapreplace(min_heap, (freq, num))
    
    # Extract elements from heap (ignore frequencies)
    result = [num for freq, num in min_heap]
    return result

• Heap for top-K problems: When you need the k largest/smallest/most frequent elements from a dataset, use a min-heap of size k (for top-k largest) or max-heap of size k (for top-k smallest) - this gives O(n log k) complexity instead of O(n log n) sorting, because you only maintain k elements in the heap at any time.
• Frequency map + heap combination: The two-step pattern of first building a frequency hashmap (O(n)) then pushing to a heap (O(n log k)) is the standard approach for frequency-based problems - separate the counting phase from the selection phase for cleaner code and optimal performance.
• Bucket sort optimization for bounded frequencies: When frequencies are bounded by array length, bucket sort achieves O(n) time by creating buckets indexed by frequency count - this trades space for time and is optimal when k is large relative to n, avoiding heap overhead entirely.
• Min-heap size maintenance: A critical implementation detail is using a min-heap of size k (not max-heap) for top-k frequent - when the heap exceeds k elements, pop the minimum, ensuring only the k most frequent remain. Many students mistakenly use max-heap which requires processing all n elements.
• Heap vs bucket sort trade-off: Choose min-heap when k is small (O(n log k) is efficient) and bucket sort when k is large or k=n (O(n) is better) - understanding this trade-off shows algorithmic maturity, as the optimal solution depends on the relationship between n and k.
• Real-world frequency analysis: This pattern appears in trending topics (Twitter's top hashtags), recommendation systems (most purchased items), log analysis (most common errors), and search autocomplete (most frequent queries) - any system that needs to surface popular items from streaming or batch data uses this exact technique.