Top K Frequent Elements

• Difficulty: Medium
• Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect
• Link: https://leetcode.com/problems/top-k-frequent-elements/

Problem Description

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

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 <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Solution

1. Problem Deconstruction

Technical Restatement
Given an array nums of integers and integer k, identify the k most frequently occurring elements. Formally:

• Let $A[0..n-1]$ be an integer array of length $n$
• Let $f: \mathbb{Z} \to \mathbb{N}$ be the frequency function $f(x) = |\{i : A[i] = x\}|$
• Find set $S \subset \text{unique}(A)$ such that $|S| = k$ and $\forall x \in S, y \notin S \implies f(x) \geq f(y)$
• Return $S$ as an ordered list (order irrelevant)

Beginner Restatement
You have a list of numbers. Count how often each number appears. Find the k numbers that appear most frequently. Return them in any order.

Mathematical Restatement
For array $A$ of size $n$:

$$S = \underset{s \subseteq \text{unique}(A), |s|=k}{\arg\max} \sum_{x \in s} f(x)$$

where $f(x) = \sum_{i=0}^{n-1} \mathbf{1}_{A[i]=x}$. Uniqueness guarantee implies strict ordering:

$$f_{(1)} > f_{(2)} > \cdots > f_{(k)} > f_{(k+1)} \geq \cdots$$

where $f_{(i)}$ is the $i$-th largest frequency.

Constraint Analysis

1. 1 <= nums.length <= 10^5
   • Rules out $O(n^2)$ brute force (e.g., 10$^{10}$ ops at $n=10^5$)
   • Requires $O(n)$ or $O(n \log k)$ solution
2. -10^4 <= nums[i] <= 10^4
   • Implies bounded distinct values $m \leq 20001$
   • Permits $O(m \log m)$ methods (since $m$ is constant-bounded)
   • Enables frequency bucket arrays of size $O(n)$
3. k ∈ [1, number of unique elements]
   • Ensures non-trivial solution ($k=0$ invalid)
   • Worst-case $k = m = 20001$ (requires heap/selection)
4. Guaranteed unique answer
   • No ties at $k$-th position: $f_{(k)} > f_{(k+1)}$
   • Simplifies termination in bucket sort (no partial bucket handling)

Hidden Edge Cases

• $k=1$: Single most frequent element (degenerate heap/sort)
• $k = m$: All distinct elements must be returned
• $n=1$: Single-element array trivially satisfies $k=1$
• Uniform frequencies (e.g., $[1,1,2,2]$, $k=1$): Prevented by uniqueness guarantee

---

2. Intuition Scaffolding

Real-World Metaphor
A music service counts song plays. With 100,000 plays and 20,001 distinct songs, find the top k played songs without full sorting (analogous to frequency counts and partial sorting).

Gaming Analogy
In an RPG, enemy types appear with varying frequency. Log all encounters (array) and prioritize defenses for the top `k$ most common enemies. Bounded enemy types (20,001) enable efficient counting.

Math Analogy
Find $k$ modes of a multiset. With bounded element domain, reduce to frequency counting and $k$-selection on frequency space.

Common Pitfalls

1. Full frequency sort ($O(m \log m)$): Valid due to bounded $m$ but violates follow-up if $m \sim n$
2. Max-heap all elements ($O(m \log m)$): Wasted work vs. min-heap of size $k$
3. Ignoring uniqueness guarantee: Unnecessary tie-breaking logic
4. Bucket index overflow: Frequencies $\leq n$, so buckets $[0..n]$ suffice
5. Premature optimization: For bounded $m$, simple sort beats complex selection

---

3. Approach Encyclopedia

Approach 1: Hash Map + Sorting

def topKFrequent(nums, k):
    freq = {}
    for num in nums:            # O(n): Build frequency map
        freq[num] = freq.get(num, 0) + 1
    
    unique_items = list(freq.items())  # O(m): Extract (num, count) pairs
    # Sort by frequency descending, extract nums
    unique_items.sort(key=lambda x: x[1], reverse=True)  # O(m log m)
    return [item[0] for item in unique_items[:k]]  # O(k)

Complexity Proof

• Time: $O(n) + O(m) + O(m \log m) + O(k) = O(n + m \log m)$
  Since $m \leq 20001$ (bounded), $O(m \log m) \approx O(1)$, total $O(n)$
• Space: $O(m)$ for map and list

Visualization

nums = [1,1,1,2,2,3], k=2
freq: {1:3, 2:2, 3:1}  
Pairs: [(1,3), (2,2), (3,1)] → Sorted: [(1,3), (2,2), (3,1)]  
Output: [1,2] (first k elements)

Approach 2: Min-Heap of Size k

import heapq

def topKFrequent(nums, k):
    freq = {}
    for num in nums:                   # O(n): Frequency map
        freq[num] = freq.get(num, 0) + 1
    
    heap = []
    for num, count in freq.items():    # O(m): Process distinct items
        heapq.heappush(heap, (count, num))  # Push (frequency, num)
        if len(heap) > k:
            heapq.heappop(heap)       # Remove smallest if > k elements
    
    return [num for count, num in heap]  # O(k)

Complexity Proof

• Time: $O(n) + O(m \log k) + O(k) = O(n + m \log k)$
  $m \leq 20001$, $k \leq m$, $\log k \leq \log 20001 \approx 15$, so $O(n)$
• Space: $O(m + k)$ (map + heap)

Visualization

freq: {1:3, 2:2, 3:1}, k=2
Heap after 1: [(3,1)]  
Heap after 2: [(2,2), (3,1)]  (min-heap: (2,2) at root)  
Add 3: [(1,3), (3,1), (2,2)] → pop (1,3) → [(2,2), (3,1)]  
Output: [2,1] (order irrelevant)

Approach 3: Bucket Sort (Optimal)

def topKFrequent(nums, k):
    freq = {}
    for num in nums:                   # O(n): Frequency map
        freq[num] = freq.get(num, 0) + 1
    
    n = len(nums)
    buckets = [[] for _ in range(n+1)] # 0..n frequency buckets
    for num, count in freq.items():    # O(m): Assign to buckets
        buckets[count].append(num)
    
    res = []
    for count in range(n, 0, -1):      # Descend frequencies
        for num in buckets[count]:     # Empty buckets skipped
            res.append(num)
            if len(res) == k:          # Terminate early
                return res
    return res

Complexity Proof

• Time: $O(n)$ (map + bucket fill + bucket traversal)
• Space: $O(n)$ (buckets array size $n+1$, total elements $m \leq n$)

Visualization

freq: {1:3, 2:2, 3:1} → Buckets:  
index: 0 1 2 3 4 5 6  
      [ ][3][2][1][ ][ ][ ]  
Traverse: index6..4 → skip, index3 → add 1 → res=[1]  
          index2 → add 2 → res=[1,2] → return

---

4. Code Deep Dive (Bucket Sort)

def topKFrequent(nums, k):
    freq = {}                           # 1. Frequency dictionary
    for num in nums:                    # 2. O(n) frequency count
        freq[num] = freq.get(num, 0) + 1  # get() handles missing keys
    
    n = len(nums)
    buckets = [[] for _ in range(n+1)]  # 3. Buckets: index = frequency
    for num, count in freq.items():     # 4. O(m) bucket assignment
        buckets[count].append(num)      # Append num to its frequency bucket
    
    res = []
    for count in range(n, 0, -1):       # 5. Descend from max frequency
        for num in buckets[count]:      # 6. Process entire bucket
            res.append(num)             # Append numbers at this frequency
            if len(res) == k:           # 7. Early termination at k elements
                return res              # Uniqueness ensures no partial bucket
    return res  # Fallback (k=0 impossible by constraints)

Edge Case Handling

• Example 1 (k=2):
  Line 2: freq becomes {1:3, 2:2, 3:1}
  Line 4: buckets[3]=[1], buckets[2]=[2], buckets[1]=[3]
  Line 7: Loop count=6→3: At count=3, res=[1]
count=2: Append 2 → res=[1,2] → return
• Example 2 (k=1):
  freq={1:1}, buckets[1]=[1] → res=[1] at first iteration
• k = m (all distinct):
  All numbers in buckets[1] → appended in order until res reaches size $k$

---

5. Complexity War Room

Hardware-Aware Analysis

• $n=10^5$ elements:
  • Frequency map: $O(n)$ time, $\approx 100$ns/element → 10 ms total
  • Buckets: Array of 100,001 pointers ($\approx$ 800 KB), fits in L2/L3 cache
  • Traversal: $O(n)$ with cache locality → $\sim$5 ms
• Total memory: $O(n)$ (buckets) + $O(m)$ (map) $\approx$ 1.2 MB, negligible

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n^2)$	$O(1)$	10	❌ (fails $n=10^5$)
Hash Map + Sort	$O(n + m \log m)$	$O(m)$	9	✅ (m bounded)
Min-Heap	$O(n + m \log k)$	$O(m)$	8	✅ (m bounded)
Bucket Sort	$\bf O(n)$	$O(n)$	9	✅✅ Optimal

---

6. Pro Mode Extras

Variants

1. Non-Unique Answer (Ties):
   • Problem: Return all elements with frequency $\geq f_{(k)}$
   • Solution: In bucket sort, collect entire bucket at $f_{(k)}$ after $k$ elements
2. Streaming Data:
   • Maintain frequency map + min-heap of size $k$
   • On each element: update map, recompute top-$k$ in $O(\log k)$
3. Top K in Sliding Window:
   • LC 347 + sliding window constraints
   • Use frequency map + heap with window-removals

Interview Cheat Sheet

• First Mention: Time/Space complexity
• Constraints: Leverage bounded $m$ or uniqueness
• Verification: Walk through examples
• Optimization Path:
  Brute Force → Hash Sort → Heap → Bucket Sort
• Edge Guards: $k=1$, $k=m$, $n=1$