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

Concept Flow - Frequency Counter Pattern Using Hash Map

Start with empty HashMap

↓

For each element in input

↓

Check if element in HashMap?

No→Add element with count 1

↓

Increment count by 1

↓

Move to next element

↓

All elements processed

↓

Return HashMap with frequencies

We start with an empty map, then for each element, we check if it exists in the map. If yes, increase count; if no, add with count 1. Repeat until all elements are counted.

Execution Sample

DSA Java

Map<String, Integer> freq = new HashMap<>();
for (String s : arr) {
  freq.put(s, freq.getOrDefault(s, 0) + 1);
}
System.out.println(freq);

This code counts how many times each string appears in the array and stores counts in a HashMap.

Execution Table

Step	Operation	Element Processed	HashMap State	Action Taken	Visual State
1	Start	-	{}	Initialize empty HashMap	{}
2	Process element	"apple"	{}	Add 'apple' with count 1	{"apple":1}
3	Process element	"banana"	{"apple":1}	Add 'banana' with count 1	{"apple":1, "banana":1}
4	Process element	"apple"	{"apple":1, "banana":1}	Increment 'apple' count to 2	{"apple":2, "banana":1}
5	Process element	"orange"	{"apple":2, "banana":1}	Add 'orange' with count 1	{"apple":2, "banana":1, "orange":1}
6	Process element	"banana"	{"apple":2, "banana":1, "orange":1}	Increment 'banana' count to 2	{"apple":2, "banana":2, "orange":1}
7	Process element	"apple"	{"apple":2, "banana":2, "orange":1}	Increment 'apple' count to 3	{"apple":3, "banana":2, "orange":1}
8	End	-	{"apple":3, "banana":2, "orange":1}	All elements processed	{"apple":3, "banana":2, "orange":1}

💡 All elements in the input array have been processed, frequency counts are complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
freq	{}	{"apple":1}	{"apple":1, "banana":1}	{"apple":2, "banana":1}	{"apple":2, "banana":1, "orange":1}	{"apple":2, "banana":2, "orange":1}	{"apple":3, "banana":2, "orange":1}	{"apple":3, "banana":2, "orange":1}

Key Moments - 3 Insights

Why do we use getOrDefault instead of just get when updating counts?

Because if the element is not yet in the map, get returns null. getOrDefault returns 0 instead, so we can safely add 1 without errors. See Step 2 where 'apple' is added with count 1.

What happens if the input array is empty?

The loop never runs, so the HashMap stays empty as shown in Step 1 and Step 8. The final map is empty, meaning no frequencies.

Why do we increment the count instead of replacing it?

Because we want to count how many times each element appears. Incrementing the existing count increases the total occurrences. See Steps 4, 6, and 7 where counts increase.

Visual Quiz - 3 Questions

Look at the execution table at Step 4. What is the count of 'apple' after processing this element?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'HashMap State' column at Step 4 in the execution table.

At which step does the HashMap first contain the key 'orange'?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for when 'orange' is added in the 'Action Taken' column.

If the input array had no repeated elements, how would the final HashMap counts look?

A All counts would be 1

B All counts would be 0

C Counts would be incremented multiple times

D HashMap would be empty

💡 Hint

Refer to the pattern of adding new keys with count 1 in the execution table.

Concept Snapshot

Frequency Counter Pattern Using Hash Map:
- Initialize empty HashMap
- For each element:
  - If key exists, increment count
  - Else, add key with count 1
- Result: Map with element frequencies
- Use getOrDefault(key, 0) to simplify counting

Full Transcript

The Frequency Counter Pattern uses a HashMap to count how many times each element appears in a collection. We start with an empty map. For each element, we check if it is already in the map. If it is, we increase its count by one. If not, we add it with count one. This process continues until all elements are processed. The final map shows the frequency of each element. Using getOrDefault helps avoid errors when keys are missing by providing a default count of zero. This pattern is useful for counting occurrences efficiently.

Practice

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

easy

A. To count how many times each element appears in a collection

B. To sort elements in ascending order

C. To store elements without duplicates

D. To reverse the order of elements

Solution

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

   A hash map stores key-value pairs, allowing quick lookup and update of counts.

2. Step 2: Apply to frequency counting

   By using elements as keys and counts as values, it tracks how many times each element appears.

3. Final Answer:

   To count how many times each element appears in a collection -> Option A

4. Quick Check:

   Frequency counting = count elements [OK]

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

Common Mistakes:

• Thinking hash map sorts elements
• Confusing frequency counting with removing duplicates
• Using hash map to reverse order

2. Which of the following is the correct way to declare a HashMap to count frequencies of characters in Java?

easy

A. HashMap freq = new HashMap<>();

B. HashMap freq = new HashMap<>();

C. HashMap<String> freq = new HashMap<>();

D. HashMap<Character> freq = new HashMap<>();

Solution

1. Step 1: Identify correct generic types for HashMap

   Keys are characters, so use Character; values are counts, so use Integer.

2. Step 2: Check syntax correctness

   HashMap freq = new HashMap<>(); is valid Java syntax.

3. Final Answer:

   HashMap freq = new HashMap<>(); -> Option B

4. Quick Check:

   Correct generics and syntax = HashMap freq = new HashMap<>(); [OK]

Hint: Use wrapper classes Character and Integer for HashMap keys and values [OK]

Common Mistakes:

• Using primitive types like int in generics
• Missing value type in HashMap declaration
• Incorrect generic syntax

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

import java.util.HashMap;
public class Main {
  public static void main(String[] args) {
    String s = "banana";
    HashMap freq = new HashMap<>();
    for (char c : s.toCharArray()) {
      freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    System.out.println(freq.get('a'));
  }
}

medium

A. 2

B. null

C. 1

D. 3

Solution

1. Step 1: Count occurrences of 'a' in "banana"

   String "banana" has 'a' at positions 1, 3, and 5, total 3 times.

2. Step 2: Check code logic for frequency counting

   Code uses getOrDefault to count each character's frequency correctly.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 'a' in "banana" = 3 [OK]

Hint: Count characters manually, then verify with getOrDefault logic [OK]

Common Mistakes:

• Counting 'a' incorrectly as 2 or 1
• Confusing getOrDefault behavior
• Expecting null for existing keys

4. Identify the error in the following Java code snippet that tries to count frequencies of integers:

import java.util.HashMap;
public class Main {
  public static void main(String[] args) {
    int[] nums = {1, 2, 2, 3};
    HashMap freq = new HashMap<>();
    for (int num : nums) {
      freq.put(num, freq.get(num) + 1);
    }
    System.out.println(freq);
  }
}

medium

A. Using freq.get(num) without checking if key exists causes NullPointerException

B. HashMap declaration is incorrect

C. The for loop syntax is invalid

D. Printing freq directly causes syntax error

Solution

1. Step 1: Analyze freq.get(num) usage inside loop

   freq.get(num) returns null if key not present, so null + 1 causes NullPointerException.

2. Step 2: Identify missing default value handling

   Code should use freq.getOrDefault(num, 0) to avoid null on first occurrence.

3. Final Answer:

   Using freq.get(num) without checking if key exists causes NullPointerException -> Option A

4. Quick Check:

   NullPointerException due to missing default value [OK]

Hint: Use getOrDefault to avoid null when key missing [OK]

Common Mistakes:

• Ignoring possibility of null from get()
• Thinking HashMap declaration is wrong
• Assuming printing freq causes error

5. Given two integer arrays arr1 and arr2, which Java code snippet correctly checks if arr2 contains the same frequency of elements as arr1 using the Frequency Counter Pattern?

hard

A. HashMap freq1 = new HashMap<>();
HashMap freq2 = new HashMap<>();
for (int n : arr1) freq1.put(n, freq1.getOrDefault(n, 0) + 1);
for (int n : arr2) freq2.put(n, freq2.getOrDefault(n, 0) + 1);
return freq1.size() == freq2.size();

B. HashMap freq = new HashMap<>();
for (int n : arr1) freq.put(n, freq.getOrDefault(n, 0) + 1);
for (int n : arr2) freq.put(n, freq.getOrDefault(n, 0) - 1);
return freq.size() == 0;

C. HashMap freq = new HashMap<>();
for (int n : arr1) freq.put(n, freq.getOrDefault(n, 0) + 1);
for (int n : arr2) freq.put(n, freq.getOrDefault(n, 0) - 1);
for (int count : freq.values()) if (count != 0) return false;
return true;

D. HashMap freq = new HashMap<>();
for (int n : arr1) freq.put(n, freq.getOrDefault(n, 0) + 1);
for (int n : arr2) freq.put(n, freq.getOrDefault(n, 0) + 1);
return freq.size() == arr1.length;

Solution

1. Step 1: Understand frequency counting for both arrays

   Count frequencies of arr1 elements positively, then subtract frequencies for arr2 elements.

2. Step 2: Verify all counts are zero

   If all counts are zero, frequencies match; otherwise, they differ.

3. Final Answer:

   Code that increments for arr1, decrements for arr2, then checks zero counts -> Option C

4. Quick Check:

   Increment then decrement counts, check zero [OK]

Hint: Add counts for arr1, subtract for arr2, verify all zero [OK]

Common Mistakes:

• Checking sizes of two separate maps instead of contents
• Adding counts for both arrays instead of subtracting
• Checking map size instead of counts