Top K Frequent Words

▶

Steps

setup

Count Frequencies of Words

Iterate over each word in the input list and count how many times each word appears, storing counts in a frequency dictionary.

💡 Counting frequencies is the foundation for grouping words by how often they appear, which is key to finding the top k frequent words.

Line:

freq = {}
for w in words:
    freq[w] = freq.get(w, 0) + 1

💡 The frequency dictionary now maps each word to its count, e.g., {'i': 2, 'love': 2, 'leetcode': 1, 'coding': 1}.

setup

Find Maximum Frequency

Determine the highest frequency count among all words to know how many buckets we need.

💡 Knowing the max frequency lets us create buckets indexed by frequency for efficient grouping.

Line:

max_freq = max(freq.values())

💡 The maximum frequency is 2, meaning we need buckets for frequencies 0, 1, and 2.

setup

Create Buckets Array

Create an array of empty buckets, where each index corresponds to a frequency from 0 to max_freq.

💡 Buckets will hold words grouped by their frequency, enabling easy retrieval of top frequent words.

Line:

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

💡 We now have 3 buckets: buckets[0], buckets[1], and buckets[2], all initially empty.

fill_row

Place Words into Buckets by Frequency

Iterate over each word and its frequency, placing the word into the bucket corresponding to its frequency count.

💡 Grouping words by frequency prepares for sorting and selecting the top k words efficiently.

Line:

for w, count in freq.items():
    buckets[count].append(w)

💡 Buckets now contain: buckets[1] = ['leetcode', 'coding'], buckets[2] = ['i', 'love'], buckets[0] = [].

traverse

Start Iterating Buckets from Highest Frequency

Begin iterating buckets from frequency 2 down to 1 to collect the most frequent words first.

💡 Starting from the highest frequency ensures we pick the most frequent words before less frequent ones.

Line:

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

💡 We will process bucket 2 first, which contains words with frequency 2.

fill_cells

Sort Bucket 2 Lexicographically

Sort the words in bucket 2 alphabetically to break ties by lexicographic order.

💡 Sorting ensures that words with the same frequency are ordered alphabetically as required.

Line:

buckets[i].sort()

💡 Bucket 2 sorted becomes ['i', 'love'].

insert

Add 'i' to Result

Add the first word 'i' from bucket 2 to the result list.

💡 Adding words from the highest frequency bucket first builds the top k list correctly.

Line:

for w in buckets[i]:
    res.append(w)
    if len(res) == k:
        return res

💡 Result list is now ['i'].

insert

Add 'love' to Result

Add the next word 'love' from bucket 2 to the result list, reaching k=2 words.

💡 Once we reach k words, we can stop and return the result.

Line:

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

💡 Result list is now ['i', 'love'], which is the final answer.

reconstruct

Prepare to Return Final Result

Prepare to return the collected top k frequent words as the final output.

💡 This step shows the final result ready to be returned by the algorithm.

Line:

return res

💡 The result list ['i', 'love'] is ready to be returned.

reconstruct

Return Final Result

Return the collected top k frequent words as the final output.

💡 Returning the result completes the algorithm and provides the answer to the problem.

Line:

return res

💡 The final answer is ['i', 'love'].

from typing import List

def topKFrequent(words: List[str], k: int) -> List[str]:
    freq = {}  # STEP 1
    for w in words:
        freq[w] = freq.get(w, 0) + 1  # STEP 1
    max_freq = max(freq.values())  # STEP 2
    buckets = [[] for _ in range(max_freq + 1)]  # STEP 3
    for w, count in freq.items():
        buckets[count].append(w)  # STEP 4
    res = []
    for i in range(max_freq, 0, -1):  # STEP 5
        if buckets[i]:
            buckets[i].sort()  # STEP 6
            for w in buckets[i]:
                res.append(w)  # STEP 7 & 8
                if len(res) == k:
                    return res  # STEP 8 & 9
    return res  # STEP 9

# Driver code
if __name__ == '__main__':
    words = ["i", "love", "leetcode", "i", "love", "coding"]
    k = 2
    print(topKFrequent(words, k))  # Expected: ['i', 'love']

📊

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

Watching each step reveals how frequency counting and bucket sorting combine to efficiently find the top k frequent words without complex heap operations.

insertmin-heap

i:2

0

love:2

1

leetcode:1

2

coding:1

3

peekmin-heap

max_freq:2

0

insertmin-heap

0

1

2

insertmin-heap

0

leetcode,coding

1

i,love

2

peekmin-heap

i

0

love

1

heapify_downmin-heap

i

0

love

1

insertmin-heap

i

0

love

1

Added: ["i"]

insertmin-heap

i

0

love

1

Added: ["i","love"]

peekmin-heap

i

0

love

1

Added: ["i","love"]

peekmin-heap

i

0

love

1

Added: ["i","love"]

Key Takeaways

✓ Frequency counting is the foundation for grouping words and finding the top k frequent words efficiently.

Without seeing the frequency dictionary build step-by-step, it's hard to grasp how the algorithm knows which words are most frequent.

✓ Using buckets indexed by frequency allows the algorithm to avoid complex heap operations and directly access words by frequency.

This bucket approach is more efficient and intuitive than building and maintaining a heap for this problem.

✓ Sorting words lexicographically within each frequency bucket ensures ties are broken correctly according to problem requirements.

This step is subtle and easy to miss when reading code, but the visualization shows how alphabetical order is enforced.

Practice

1. You need to design a data structure that supports two operations: push(val) which adds an integer to the structure, and pop() which removes and returns the most frequent element. If multiple elements have the same highest frequency, the most recently added among them is removed first. Which approach guarantees optimal time complexity for both operations?

easy

A. Maintain a frequency map and a max-heap keyed by frequency and recency (timestamp) to pop the correct element efficiently.

B. Use dynamic programming to precompute frequencies and then pop elements in order.

C. Use a priority queue keyed only by frequency, ignoring insertion order.

D. Use a single stack and scan it on each pop to find the most frequent element.

Solution

1. Step 1: Understand the problem constraints

   The data structure must return the element with the highest frequency, and if there's a tie, the most recently pushed element among them.

2. Step 2: Evaluate approaches

   Approach A is brute force and inefficient. Approach C ignores recency, so it fails tie-breaking. Approach B uses dynamic programming which is unrelated and inefficient for this problem. Approach D maintains a frequency map and a max-heap keyed by frequency and timestamp, ensuring O(log n) push and pop operations with correct tie-breaking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap with frequency and timestamp ensures correct order and efficiency [OK]

Hint: Max-heap with freq and timestamp breaks ties correctly [OK]

Common Mistakes:

• Ignoring recency in tie-breaking
• Using a single stack and scanning on pop
• Confusing DP with frequency tracking

2. 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

3. Suppose the problem is modified so that pairs can be formed with repeated elements (i.e., pairs like (nums[i], nums[i]) are allowed, distance 0). Which modification to the heap-based approach correctly handles this variant?

hard

A. Modify the heap initialization to include pairs (nums[i] - nums[i], i, i) and also pairs (nums[i+1] - nums[i], i, i+1), then proceed with the same loop.

B. Initialize the heap with pairs from adjacent elements as before, but add an extra step to push pairs with identical indices after popping.

C. Initialize the heap with pairs (nums[i] - nums[i], i, i) for all i, then proceed as usual.

D. Use the same heap initialization but increase k by the number of elements to account for zero-distance pairs.

Solution

1. Step 1: Understand zero-distance pairs

   Pairs with identical indices (i,i) have distance 0 and must be included in the heap initialization.

2. Step 2: Modify heap initialization

   Include pairs (nums[i]-nums[i], i, i) for all i, plus pairs from adjacent elements to cover all pairs including zero-distance.

3. Step 3: Proceed with the same pop-push loop

   Heap operations remain unchanged, ensuring correct k-th smallest distance including zero-distance pairs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Including (i,i) pairs ensures zero distances are counted [OK]

Hint: Add zero-distance pairs explicitly to heap initialization [OK]

Common Mistakes:

• Ignoring zero-distance pairs
• Trying to adjust k instead of heap
• Pushing zero-distance pairs only after popping

4. Suppose the frequency stack must support a new operation popK(k) that removes and returns the top k most frequent elements in order, breaking ties by recency. Which modification to the optimal heap-based approach correctly supports this operation efficiently?

hard

A. Perform k consecutive pop() calls on the heap, updating frequencies after each pop.

B. Use a separate max-heap for each frequency level and merge results on popK(k).

C. Modify the heap to store lists of elements per frequency and pop from these lists in order.

D. Maintain a global sorted list of elements by frequency and recency, and slice the top k on popK(k).

Solution

1. Step 1: Understand popK(k) requirements

   We must pop the top k elements by frequency and recency order, updating frequencies after each pop.

2. Step 2: Evaluate modifications

   Perform k consecutive pop() calls on the heap, updating frequencies after each pop. This performs k pops sequentially, each O(log n), correctly updating frequencies and maintaining heap invariants. Options A, B, and D either complicate the data structure or lose efficiency and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sequential pops maintain correctness and efficiency [OK]

Hint: Sequential pops maintain heap correctness for top-k [OK]

Common Mistakes:

• Trying to pop multiple elements at once without updating frequencies
• Using complex data structures that break heap invariants

5. Suppose the problem changes: you want to find the kth largest XOR coordinate value, but now the matrix can contain negative integers. Which modification to the optimal prefix XOR + min-heap approach is necessary to handle this correctly?

hard

A. Use a 64-bit integer type to store prefix XOR values to avoid sign issues.

B. Convert all negative integers to positive before computing prefix XOR.

C. No modification needed; XOR works the same with negative integers.

D. Use bitwise AND instead of XOR to handle negative values correctly.

Solution

1. Step 1: Understand XOR with negative integers

   In Python, integers are unbounded but negative numbers use two's complement representation internally, which can cause sign extension issues if stored in fixed-width types.

2. Step 2: Use 64-bit integer type for prefix XOR

   To correctly handle negative values and avoid sign extension or overflow, use a 64-bit integer type (e.g., numpy.int64) for prefix XOR computations and heap storage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Handling negative integers requires careful data type choice, not changing XOR logic [OK]

Hint: XOR logic unchanged; data type must handle sign correctly [OK]

Common Mistakes:

• Assuming XOR fails with negatives
• Replacing XOR with AND
• Ignoring integer overflow/sign issues