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. You are given two integer arrays and need to find all elements that appear in both arrays, including duplicates, with the output containing each common element as many times as it appears in both arrays. Which approach guarantees the most efficient solution in terms of time complexity for large inputs?

easy

A. Sort both arrays and use two pointers to traverse them simultaneously, collecting common elements.

B. Use dynamic programming to build a table of common elements counts.

C. Use nested loops to check each element of the first array against all elements of the second array.

D. Use a greedy approach to pick elements from the first array that appear earliest in the second array.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding all common elements including duplicates, so a method that preserves counts is needed.

2. Step 2: Evaluate approaches

   Sorting both arrays and using two pointers allows linear traversal after sorting, efficiently finding all duplicates. Nested loops are O(m*n), DP is not applicable here, and greedy does not guarantee correct counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is O(m log m + n log n) and handles duplicates correctly [OK]

Hint: Sorting + two pointers handles duplicates efficiently [OK]

Common Mistakes:

• Thinking nested loops are efficient enough
• Confusing DP applicability
• Assuming greedy works for duplicates

2. Consider the following code snippet implementing the optimal approach for longest consecutive sequence. What is the value of max_len returned when the input is [1, 9, 3, 10, 2]?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Identify sequence starts

   Numbers are {1,2,3,9,10}. Sequence starts are numbers where num-1 not in set: 1 and 9.

2. Step 2: Count consecutive lengths

   From 1: sequence is 1,2,3 -> length 3. From 9: sequence is 9,10 -> length 2. Max length is 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest consecutive sequence is [1,2,3] length 3 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number causing duplicates
• Off-by-one errors in length counting
• Confusing max length with total unique numbers

3. You are given an array of integers and a target integer. You need to find two distinct elements in the array whose sum equals the target. Which approach guarantees finding the solution in linear time on average?

easy

A. Use a hash map to store elements and check for complements during a single pass.

B. Use a greedy approach by picking the largest number and searching for its complement.

C. Use dynamic programming to build up sums and check for the target.

D. Sort the array and use two pointers to find the pair summing to the target.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding two distinct elements whose sum equals the target efficiently.

2. Step 2: Evaluate approaches

   A greedy approach does not guarantee correctness; dynamic programming is unnecessary overhead; sorting + two pointers is O(n log n). Using a hash map allows O(n) average time by checking complements in one pass.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map lookup enables linear time complement checks [OK]

Hint: Hash map lookup enables O(n) complement checks [OK]

Common Mistakes:

• Confusing sorting + two pointers as linear time
• Assuming greedy approach works for sums
• Misapplying DP to Two Sum

4. Identify the bug in the following code snippet for grouping anagrams:

medium

A. Line 4: defaultdict initialization

B. Line 7: Incrementing count array

C. Line 10: Appending string to map

D. Line 9: Using ''.join(count) to create key

Solution

1. Step 1: Understand key creation

   Count is a list of integers; ''.join(count) tries to join integers as strings, causing TypeError or incorrect keys.

2. Step 2: Correct key creation

   Key should be a tuple of counts to be hashable and unique, e.g., key = tuple(count).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using ''.join on int list causes errors or wrong grouping [OK]

Hint: Keys must be hashable types like tuples, not joined strings of ints [OK]

Common Mistakes:

• Joining int list without conversion
• Using list as dict key
• Forgetting to convert count to tuple

5. Suppose the problem is modified so that characters in s can be reused multiple times to map to characters in t (i.e., the mapping is many-to-one, not one-to-one). Which of the following approaches correctly adapts the isomorphic strings check to this new requirement?

hard

A. Use nested loops to check all pairs for consistency as in brute force

B. Keep bidirectional hash maps but allow multiple s chars to map to the same t char

C. Sort both strings and compare if sorted strings are equal

D. Use only a single hash map from s to t without reverse mapping checks

Solution

1. Step 1: Understand the relaxed mapping constraint

   Since multiple characters in s can map to the same character in t, the reverse mapping from t to s is no longer one-to-one and need not be checked.

2. Step 2: Adapt the algorithm

   Using a single hash map from s to t suffices to ensure each s character maps consistently, ignoring reverse mapping.

3. Step 3: Evaluate other options

   Bidirectional maps are unnecessary and would incorrectly reject valid mappings; brute force is inefficient; sorting does not preserve character positions.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Single-direction mapping fits many-to-one mapping requirement [OK]

Hint: Relaxed mapping removes need for reverse checks [OK]

Common Mistakes:

• Keeping bidirectional checks unnecessarily
• Using brute force causing inefficiency
• Sorting strings which breaks order