Top K Frequent Elements

▶

Steps

setup

Initialize frequency map as empty

We start with an empty hash map to count frequencies of elements in nums.

💡 Initializing the frequency map is essential to start counting how many times each element appears.

Line:

freq = {}

💡 The frequency map will store each unique element as a key and its count as the value.

fill_row

Process first element 1: insert with count 1

Element 1 is not in freq, so we insert it with count 1.

💡 When an element appears for the first time, it must be added to the map with count 1.

Line:

freq[num] = freq.get(num, 0) + 1

💡 The map now tracks that element 1 has appeared once.

fill_row

Process second element 1: increment count to 2

Element 1 is found in freq with count 1, so we increment its count to 2.

💡 Incrementing counts for repeated elements updates their frequency in the map.

Line:

freq[num] = freq.get(num, 0) + 1

💡 The map reflects that element 1 has appeared twice now.

fill_row

Process third element 1: increment count to 3

Element 1 is found again; increment its count from 2 to 3.

💡 Each occurrence of the same element increases its frequency count.

Line:

freq[num] = freq.get(num, 0) + 1

💡 Element 1 now has the highest frequency so far: 3.

fill_row

Process fourth element 2: insert with count 1

Element 2 is new, so insert it with count 1.

💡 New elements are added to the map with initial count 1.

Line:

freq[num] = freq.get(num, 0) + 1

💡 The map now tracks element 2 with count 1.

fill_row

Process fifth element 2: increment count to 2

Element 2 found with count 1, increment to 2.

💡 Repeated elements update their frequency counts.

Line:

freq[num] = freq.get(num, 0) + 1

💡 Element 2 frequency is now 2.

fill_row

Process sixth element 3: insert with count 1

Element 3 is new, insert with count 1.

💡 New elements are added with initial count 1.

Line:

freq[num] = freq.get(num, 0) + 1

💡 Frequency map now contains all unique elements with their counts.

setup

Determine max frequency from freq map

Find the maximum frequency value among all elements to size buckets.

💡 Knowing max frequency lets us create buckets indexed by frequency.

Line:

max_freq = max(freq.values())

💡 Max frequency is 3, so buckets array will have length 4 (0 to 3).

setup

Create empty buckets array indexed by frequency

Create an array of empty lists where index represents frequency from 0 to max_freq.

💡 Buckets will group elements by their frequency for easy retrieval.

Line:

buckets = [[] for _ in range(max_freq + 1)]

💡 Buckets array has 4 empty lists: buckets[0], buckets[1], buckets[2], buckets[3].

fill_cells

Place element 1 into bucket for frequency 3

Element 1 has frequency 3, so add it to buckets[3].

💡 Placing elements into buckets groups them by how often they appear.

Line:

buckets[count].append(num)

💡 Bucket 3 now contains [1].

fill_cells

Place element 2 into bucket for frequency 2

Element 2 has frequency 2, add it to buckets[2].

💡 Elements with same frequency share the same bucket.

Line:

buckets[count].append(num)

💡 Bucket 2 now contains [2].

fill_cells

Place element 3 into bucket for frequency 1

Element 3 has frequency 1, add it to buckets[1].

💡 Lowest frequency elements go into the lowest index bucket.

Line:

buckets[count].append(num)

💡 Bucket 1 now contains [3].

traverse

Start collecting top k elements from highest frequency bucket

Begin iterating buckets from index 3 down to 1 to collect elements until k=2 are found.

💡 We want the most frequent elements first, so start from highest frequency bucket.

Line:

for i in range(max_freq, 0, -1):

💡 Bucket 3 contains [1], so element 1 is added first.

insert

Add element 1 to result list

Element 1 is appended to the result list as it is the most frequent.

💡 Collecting elements in order of frequency builds the final answer.

Line:

res.append(num)

💡 Result list now contains [1].

traverse

Move to next bucket with frequency 2

Check bucket 2 which contains [2] to add next most frequent element.

💡 We continue collecting elements from next highest frequency bucket.

Line:

for num in buckets[i]:

💡 Element 2 is next most frequent and will be added.

insert

Add element 2 to result list

Element 2 is appended to the result list, reaching k=2 elements.

💡 Once k elements are collected, the algorithm can return the result.

Line:

res.append(num)
if len(res) == k:
    return res

💡 Result list is [1, 2], the top 2 frequent elements.

reconstruct

Final result returned

The algorithm returns the list [1, 2] as the top k frequent elements.

💡 The final output is the collected list of most frequent elements.

Line:

return res

💡 The algorithm successfully identified the top 2 frequent elements.

from typing import List

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}  # STEP 1: Initialize frequency map
    for num in nums:
        freq[num] = freq.get(num, 0) + 1  # STEP 2-7: Count frequencies
    max_freq = max(freq.values())  # STEP 8: Find max frequency
    buckets = [[] for _ in range(max_freq + 1)]  # STEP 9: Create buckets
    for num, count in freq.items():
        buckets[count].append(num)  # STEP 10-12: Place elements in buckets
    res = []
    for i in range(max_freq, 0, -1):  # STEP 13,15: Traverse buckets from high to low
        for num in buckets[i]:
            res.append(num)  # STEP 14,16: Collect elements
            if len(res) == k:
                return res  # STEP 16: Return when k elements collected
    return res  # STEP 17: Return result if loop ends

if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

📊

Top K Frequent Elements - Watch the Algorithm Execute, Step by Step

Watching each step of frequency counting and bucket placement helps you understand how the algorithm efficiently finds the most frequent elements without sorting the entire input.

insert

empty map

insert

Lookup: 1

1→1lookup

increment

Lookup: 1→ 2

1→2lookup

increment

Lookup: 1→ 3

1→3lookup

insert

Lookup: 2

1→3

2→1lookup

increment

Lookup: 2→ 2

1→3

2→2lookup

insert

Lookup: 3

1→3

2→2

3→1lookup

check

1→3

2→2

3→1

insert

empty map

insert

Lookup: 1→ 3

1→3lookup

insert

Lookup: 2→ 2

1→3

2→2lookup

insert

Lookup: 3→ 1

1→3

2→2

3→1lookup

lookup

Lookup: 3→ [1]

empty map

Result: [1]

insert

empty map

Result: [1]

lookup

Lookup: 2→ [2]

empty map

Result: [1]

insert

empty map

Result: [1,2]

check

empty map

Result: [1,2]

Key Takeaways

✓ Frequency counting with a hash map efficiently tracks how often each element appears.

This insight is hard to see from code alone because the map updates happen quickly and implicitly.

✓ Grouping elements into buckets by frequency allows quick access to the most frequent elements without sorting.

Visualizing buckets clarifies why this approach is more efficient than sorting all elements by frequency.

✓ Traversing buckets from highest to lowest frequency ensures the top k elements are collected in correct order.

Seeing the traversal and early return helps understand how the algorithm stops as soon as enough elements are found.

Practice

1. Consider the following Python code implementing the optimal approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,5],[6,10]] and k = 3, what is the final returned value?

easy

A. 6

B. 5

C. 10

D. 1

Solution

1. Step 1: Trace countLessEqual(mid) for mid=5

   Count elements ≤5: row=1,col=0; matrix[1][0]=6>5 -> row=0; matrix[0][0]=1≤5 -> count=1, col=1; matrix[0][1]=5≤5 -> count=2, col=2 (end). Total=2 < k=3.

2. Step 2: Update low=mid+1=6, repeat binary search

   Now low=6, high=10; mid=8; countLessEqual(8) counts elements ≤8: row=1,col=0; matrix[1][0]=6≤8 -> count=2, col=1; matrix[1][1]=10>8 -> row=0; matrix[0][1]=5≤8 -> count=3, col=2 (end). Total=3 ≥ k=3, so high=mid=8.

3. Step 3: Continue binary search until low=high=6

   Eventually low converges to 6, which is the 3rd smallest element.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search narrows to 6 as 3rd smallest [OK]

Hint: Count elements ≤ mid guides binary search [OK]

Common Mistakes:

• Off-by-one in k indexing
• Miscounting elements ≤ mid

2. You are given a string and need to return a new string where characters are sorted by their frequency in descending order. Which approach guarantees an optimal O(n) time complexity solution for this problem?

easy

A. Use a greedy approach that repeatedly picks the character with the highest frequency without precomputing frequencies.

B. Use dynamic programming to build solutions for substrings based on character counts.

C. Use bucket sort by frequency: count frequencies, group characters by frequency, then concatenate from highest to lowest frequency.

D. Use a min-heap to store characters by frequency and extract them one by one.

Solution

1. Step 1: Understand frequency grouping

   Counting frequencies and grouping characters by frequency allows linear time sorting by frequency.

2. Step 2: Why bucket sort is optimal

   Bucket sort avoids sorting all characters explicitly, achieving O(n) time by iterating frequency buckets.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket sort groups by frequency and concatenates in descending order [OK]

Hint: Bucket sort groups chars by frequency for linear time [OK]

Common Mistakes:

• Using min-heap without negation leads to ascending order
• Greedy without frequency count misses optimal order

3. What is the time complexity of the pop() operation in the optimal frequency stack implementation that uses a max-heap keyed by frequency and timestamp, assuming n total operations?

medium

A. O(1) amortized, since the heap is balanced automatically

B. O(log n), due to heap pop operation on at most n elements

C. O(n), because frequencies must be recomputed on each pop

D. O(log k), where k is the number of distinct elements

Solution

1. Step 1: Identify heap size and operations

   The heap stores one entry per push operation, so its size can be up to n.

2. Step 2: Analyze pop complexity

   Each pop calls heapq.heappop which takes O(log n) time in worst case. Frequency map updates are O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap pop dominates time complexity, so O(log n) per pop [OK]

Hint: Heap pop is O(log n), not O(1) or O(n) [OK]

Common Mistakes:

• Assuming heap pop is O(1)
• Confusing frequency recomputation cost
• Assuming complexity depends on distinct elements only

4. The following code attempts to implement the optimal frequency stack using a max-heap with timestamp. Identify the bug that causes incorrect behavior when popping elements.

import heapq

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.heap = []
        self.time = 0

    def push(self, val: int) -> None:
        self.freq[val] = self.freq.get(val, 0) + 1
        self.time += 1
        heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

    def pop(self) -> int:
        freq, time, val = heapq.heappop(self.heap)
        # BUG: Missing frequency decrement
        if self.freq[val] == 0:
            del self.freq[val]
        return val

medium

A. Line with heapq.heappop(self.heap) does not pop the correct element.

B. Frequency map deletion condition is incorrect; should delete when freq[val] == 1.

C. Timestamp is not updated on push, so recency is lost.

D. Frequency map is not decremented after popping, causing stale frequencies.

Solution

1. Step 1: Identify frequency update after pop

   The code does not decrement frequency after popping an element, so freq[val] remains stale.

2. Step 2: Consequences of missing decrement

   Without decrement, future pushes and pops will have incorrect frequency counts, breaking the max frequency logic.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Frequency must be decremented after pop to maintain correctness [OK]

Hint: Always decrement frequency after popping an element [OK]

Common Mistakes:

• Forgetting to update frequency map after pop
• Mismanaging timestamp updates
• Incorrect deletion condition for frequency map

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent words from a list of n words, assuming the maximum frequency is m and average word length is constant?

medium

A. O(n log n) due to sorting all unique words

B. O(n m) because sorting words within buckets depends on max frequency m

C. O(n) because frequency counting and bucket placement are linear, and sorting within buckets is bounded

D. O(k log n) because extracting top k from a heap dominates

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies is O(n) since each word is processed once.

2. Step 2: Analyze bucket placement and sorting

   Words are placed into buckets indexed by frequency; sorting within each bucket is lexicographic but total words sum to n, so total sorting cost is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall time is linear in n with lex sort bounded by total words [OK]

Hint: Bucket sort + lex sort within buckets is O(n) total [OK]

Common Mistakes:

• Assuming full sort is needed (O(n log n))
• Confusing max frequency m as multiplicative factor
• Thinking heap extraction dominates