Frequency Counter Pattern Using Hash Map in DSA Rust - Execution Trace

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty hash map

↓

Read next element from input

↓

Is element in hash map?

No→Add element with count 1

|Yes↓

Increment element count by 1

↓

More elements?

Yes→Read next element

No↓

Return hash map with frequencies

We start with an empty hash map, read each element, add or update its count, and finally return the map with all frequencies.

Execution Sample

DSA Rust

use std::collections::HashMap;

let arr = [2, 3, 2, 4, 3];
let mut freq = HashMap::new();
for &num in arr.iter() {
    *freq.entry(num).or_insert(0) += 1;
}
println!("{:?}", freq);

This code counts how many times each number appears in the array using a hash map.

Execution Table

Step	Operation	Element Processed	Hash Map State	Visual State
1	Start	-	{}	{}
2	Process element	2	{"2": 1}	{2:1}
3	Process element	3	{"2": 1, "3": 1}	{2:1} -> {3:1}
4	Process element	2	{"2": 2, "3": 1}	{2:2} -> {3:1}
5	Process element	4	{"2": 2, "3": 1, "4": 1}	{2:2} -> {3:1} -> {4:1}
6	Process element	3	{"2": 2, "3": 2, "4": 1}	{2:2} -> {3:2} -> {4:1}
7	End	-	{"2": 2, "3": 2, "4": 1}	{2:2} -> {3:2} -> {4:1}

💡 All elements processed, frequency map complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
freq	{}	{"2":1}	{"2":1, "3":1}	{"2":2, "3":1}	{"2":2, "3":1, "4":1}	{"2":2, "3":2, "4":1}	{"2":2, "3":2, "4":1}
element	-	2	3	2	4	3	-

Key Moments - 3 Insights

Why do we check if the element exists in the hash map before incrementing?

Because if the element is not yet in the map, we must add it with count 1. This is shown in steps 2 and 3 where new elements are added.

What happens when the same element appears again?

We find it in the map and increase its count by 1, as seen in steps 4 and 6 where counts for '2' and '3' are incremented.

Why is the hash map empty at the start?

We start with an empty map to ensure counts are accurate only for elements processed, as shown in step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the frequency of element '3' after step 3?

A 0

B 2

C 1

D 3

💡 Hint

Check the 'Hash Map State' column at step 3 in the execution table.

At which step does the frequency of element '2' become 2?

A Step 4

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Hash Map State' column for element '2' in the execution table.

If the input array had one more '4' at the end, what would be the final frequency of '4'?

A 1

B 2

C 3

D 4

💡 Hint

Consider how frequencies increment when the same element appears again, as shown in steps 4 and 6.

Concept Snapshot

Frequency Counter Pattern using Hash Map:
- Start with empty hash map
- For each element:
  - If not in map, add with count 1
  - Else increment count
- Result: map with element frequencies
- Useful for counting duplicates or comparing collections

Full Transcript

The Frequency Counter Pattern uses a hash map to count how many times each element appears in a collection. We start with an empty map. For each element, we check if it exists in the map. If not, we add it with count 1. If yes, we increase its count by 1. After processing all elements, the map holds the frequency of each element. This pattern helps quickly count duplicates or compare data sets efficiently.

Practice

1. What is the main purpose of using a hash map in the Frequency Counter Pattern?

easy

A. To remove duplicate items from the collection

B. To sort the items in ascending order

C. To count how many times each item appears in a collection

D. To reverse the order of items in the collection

Solution

1. Step 1: Understand the role of a hash map

   A hash map stores key-value pairs, allowing quick lookup of counts for each item.

2. Step 2: Connect to frequency counting

   Using the hash map, we track how many times each item appears by updating counts.

3. Final Answer:

   To count how many times each item appears in a collection -> Option C

4. Quick Check:

   Frequency counting = Counting items [OK]

Hint: Hash map keys track items, values track counts [OK]

Common Mistakes:

• Thinking hash map sorts items
• Confusing frequency counting with removing duplicates
• Assuming hash map reverses order

2. Which of the following Rust code snippets correctly initializes an empty hash map for frequency counting?

easy

A. let mut freq = Vec::with_capacity(10);

B. let freq = Vec::new();

C. let freq = HashSet::new();

D. let mut freq = HashMap::new();

Solution

1. Step 1: Identify the correct data structure for frequency counting

   Frequency counting requires a hash map to store keys and counts.

2. Step 2: Check Rust syntax for hash map initialization

   In Rust, HashMap::new() creates an empty hash map; mut allows modification.

3. Final Answer:

   let mut freq = HashMap::new(); -> Option D

4. Quick Check:

   HashMap::new() initializes empty map [OK]

Hint: Use HashMap::new() with mut for frequency map [OK]

Common Mistakes:

• Using Vec or HashSet instead of HashMap
• Forgetting mut keyword to modify map
• Confusing capacity with initialization

3. What will be the output of the following Rust code?

use std::collections::HashMap;

fn main() {
    let items = vec!["apple", "banana", "apple", "orange", "banana", "apple"];
    let mut freq = HashMap::new();

    for item in items {
        let count = freq.entry(item).or_insert(0);
        *count += 1;
    }

    println!("{:?}", freq);
}

medium

A. {"apple": 1, "banana": 1, "orange": 1}

B. {"apple": 3, "banana": 2, "orange": 1}

C. {"apple": 2, "banana": 2, "orange": 2}

D. Compilation error due to missing mut

Solution

1. Step 1: Count occurrences of each fruit

   "apple" appears 3 times, "banana" 2 times, "orange" 1 time in the vector.

2. Step 2: Check how counts are updated in the hash map

   Each item increments its count correctly using entry and or_insert.

3. Final Answer:

   {"apple": 3, "banana": 2, "orange": 1} -> Option B

4. Quick Check:

   Count each fruit correctly = {"apple":3,"banana":2,"orange":1} [OK]

Hint: Count each item incrementally with entry().or_insert(0) [OK]

Common Mistakes:

• Assuming counts start at 1 instead of 0
• Forgetting to dereference count to increment
• Confusing output format or order

4. Identify the error in this Rust code snippet for frequency counting:

use std::collections::HashMap;

fn main() {
    let items = vec!["cat", "dog", "cat"];
    let mut freq = HashMap::new();

    for item in items {
        let count = freq.entry(item).or_insert(1);
        *count += 1;
    }

    println!("{:?}", freq);
}

medium

A. or_insert should start with 0, not 1

B. Missing mut keyword for freq

C. Cannot use entry on a vector

D. Dereferencing count is not needed

Solution

1. Step 1: Understand or_insert initial value

   or_insert(1) sets initial count to 1, but counting starts from zero.

2. Step 2: Effect of starting at 1 on counts

   Starting at 1 causes counts to be off by one; correct is or_insert(0).

3. Final Answer:

   or_insert should start with 0, not 1 -> Option A

4. Quick Check:

   Frequency count starts at zero [OK]

Hint: Start counts at 0 with or_insert(0) [OK]

Common Mistakes:

• Starting count at 1 inflates frequencies
• Forgetting mut on freq (not error here)
• Misunderstanding dereference necessity

5. Given a list of words, how would you use the Frequency Counter Pattern with a hash map in Rust to find all words that appear exactly twice? Choose the best approach.

hard

A. Count frequencies with a hash map, then collect keys with value 2 into a vector

B. Sort the list and pick every second word

C. Use a hash set to store words and print those that appear twice

D. Count frequencies but ignore words appearing more than once

Solution

1. Step 1: Use hash map to count all word frequencies

   Traverse the list, increment counts for each word in the hash map.

2. Step 2: Filter keys with frequency exactly two

   Iterate over the hash map entries and collect words with count == 2.

3. Final Answer:

   Count frequencies with a hash map, then collect keys with value 2 into a vector -> Option A

4. Quick Check:

   Frequency count + filter for 2 = correct approach [OK]

Hint: Count all, then filter keys with count 2 [OK]

Common Mistakes:

• Sorting does not guarantee frequency counts
• Hash set cannot count duplicates
• Ignoring words with frequency > 1 loses needed data