Frequency Counter Pattern Using Hash Map in DSA Java

Mental Model

Count how many times each item appears by using a map that links items to their counts.

Analogy: Imagine counting how many apples, oranges, and bananas you have by writing down each fruit and the number next to it on a piece of paper.

Array: [a, b, a, c, b, a]
HashMap:
 a -> 3
 b -> 2
 c -> 1

Dry Run Walkthrough

Input: array: [a, b, a, c, b, a]

Goal: Count how many times each letter appears in the array

Step 1: Read first element 'a', add 'a' to map with count 1

HashMap: a -> 1

Why: Start counting by adding the first item with count 1

Step 2: Read second element 'b', add 'b' to map with count 1

HashMap: a -> 1, b -> 1

Why: New item 'b' found, add it with count 1

Step 3: Read third element 'a', increase count of 'a' to 2

HashMap: a -> 2, b -> 1

Why: Item 'a' already in map, increase its count

Step 4: Read fourth element 'c', add 'c' to map with count 1

HashMap: a -> 2, b -> 1, c -> 1

Why: New item 'c' found, add it with count 1

Step 5: Read fifth element 'b', increase count of 'b' to 2

HashMap: a -> 2, b -> 2, c -> 1

Why: Item 'b' already in map, increase its count

Step 6: Read sixth element 'a', increase count of 'a' to 3

HashMap: a -> 3, b -> 2, c -> 1

Why: Item 'a' already in map, increase its count

Result:

HashMap: a -> 3, b -> 2, c -> 1

Annotated Code

DSA Java

import java.util.HashMap;
import java.util.Map;

public class FrequencyCounter {
    public static Map<Character, Integer> countFrequency(char[] arr) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : arr) {
            if (freqMap.containsKey(ch)) {
                freqMap.put(ch, freqMap.get(ch) + 1); // increase count
            } else {
                freqMap.put(ch, 1); // first occurrence
            }
        }
        return freqMap;
    }

    public static void main(String[] args) {
        char[] input = {'a', 'b', 'a', 'c', 'b', 'a'};
        Map<Character, Integer> result = countFrequency(input);
        for (Map.Entry<Character, Integer> entry : result.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

if (freqMap.containsKey(ch)) {

Check if character already counted

freqMap.put(ch, freqMap.get(ch) + 1); // increase count

Increase count for existing character

freqMap.put(ch, 1); // first occurrence

Add new character with count 1

Output

a -> 3

b -> 2

c -> 1

Complexity Analysis

Time: O(n) because we go through each element once to count

Space: O(k) where k is number of unique elements stored in the map

vs Alternative: Better than nested loops O(n^2) because map lookup and insert are O(1) on average

Edge Cases

empty array

returns empty map with no counts

DSA Java

for (char ch : arr) {

array with one element

map contains that element with count 1

DSA Java

freqMap.put(ch, 1); // first occurrence

array with all identical elements

map contains one key with count equal to array length

DSA Java

freqMap.put(ch, freqMap.get(ch) + 1); // increase count

When to Use This Pattern

When you need to count how many times items appear in a collection, use the frequency counter pattern with a hash map for fast counting.

Common Mistakes

Mistake: Forgetting to check if the item is already in the map before increasing count
Fix: Always check with containsKey before updating count, else add with count 1

Summary

Counts how many times each item appears using a hash map.

Use when you need quick frequency counts of elements in a list or array.

The key insight is to store counts in a map keyed by the item for O(1) updates.

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