Frequency Counter Pattern

Introduction: The Halloween Candy Sorting Notebook

Imagine it is Halloween night! You and your best friend just got home with big pillowcases full of yummy treats. You want to see if your friend got the exact same mix of candies as you!

You have two choices to solve this mystery:

1. The Slow Candy-by-Candy Search (Brute Force): You pull out a Lollipop from your bag. You reach into your friend's bag and search through every single candy one-by-one until you find a Lollipop. If you find one, you cross both off and grab a Hershey Bar, searching their bag all over again. If you both have N candies, this takes forever: up to N * N operations! In computer science, this is O(n^2) time complexity. Your candy will melt before you finish!
2. The Candy Inventory Notebook (Frequency Counter): You grab a small notebook. You empty your bag and go through your candy pile just once, making a quick tally mark next to a drawing of each candy: {🍭: 5, 🍫: 2, 🐻: 7}. This is super fast: O(n) linear time! Your friend does the exact same thing with their bag in another list. Finally, you just sit back and compare the two lists in your notebook. You'll be done in minutes!

In computer science, the Frequency Counter pattern is a neat trick where we use a notebook (like a Hash Map, a Hash Set, or a fixed-size array) to keep track of how many times each item appears in a collection. By using this notebook, we avoid nesting loops (O(n^2)) and instead check everything in a single, fast, linear pass (O(n)).

---

Anatomy and Mechanics of Frequency Counting

Depending on what we are counting, we write our notebook using one of two structures:

1. Hash Maps (For Any Kind of Keys)

Use this when your keys are dynamic and unpredictable, like words, large numbers, or custom objects.

• How it works: You start with an empty map. For each item you see, you ask: "Is this already in my map?" If yes, you add 1 to its count. If no, you write it down with a count of 1.
• Speed: Super fast! Finding or updating a key takes O(1) constant time on average.

2. Fixed-Size Arrays (For Constrained Alphabets)

If you are only counting simple, limited things—like lowercase English letters (a to z)—you don't even need a full Hash Map. You can draw 26 chalk circles on the sidewalk, labeled 0 to 25!

• How it works: An array of size 26 is initialized to all zeros. You map each letter to a number index by subtracting the base character's ASCII value (e.g., char - 'a').
• Why it's awesome: It uses almost zero memory, requires no complex hashing calculations, and is incredibly fast!

Sidewalk Chalk Circle:   'a'    'b'    'c'   ...    'z'
Array Index Map:         0      1      2    ...     25
Candy Count:           [ 5 ]  [ 0 ]  [ 2 ]  ...   [ 1 ]

---

Operations & Complexity Profile

Here is how a frequency counter notebook beats brute force nested loops:

---

Core Algorithmic Patterns and Templates

Let's master the three primary interview variations of the Frequency Counter pattern.

Pattern 1: Multi-Collection Frequency Matching (Valid Anagram)

Given two strings S and T, return true if T is an anagram of S (rearranged characters), and false otherwise.

The Strategy

1. If the strings have different lengths, return false immediately.
2. Build a frequency tally of the characters in the first string.
3. Iterate through the second string, decrementing the counts in your tally. If a character is not in the tally or its count drops below 0, return false.
4. If the loop completes successfully, return true.

Complete Implementations

Trace Table: s = "anagram", t = "nagaram"

---

Pattern 2: Category Hash Grouping (Group Anagrams)

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

The Strategy

1. We need a way to represent the frequency "signature" of a word.
2. Since words that are anagrams share the exact same character counts, we can create a signature array of size 26 for each word, convert it to a tuple or string (e.g., "1,0,3,...0"), and use that signature as a Hash Map key.
3. Group each word under its signature list in the Hash Map, then return the map's grouped values.

Complete Implementations

---

Common Interview Pitfalls and Debugging Strategies

Frequency counters are highly efficient but can break due to language-specific map behaviors:

1. Key Conversion / Comparison Failures

• The Pitfall: In JavaScript/TypeScript, using an array as a map key checks reference identity, not content. Thus, map.set([1, 2], 'val') and map.get([1, 2]) will return undefined because the two arrays have different memory references.
• The Solution: Always convert your array or object signatures into primitive data structures (like a string or comma-separated list: count.join(',')) when using them as keys in JavaScript/TypeScript. In Python, use immutable tuples: tuple(count).

2. Missing Defaults on Map Retrievals

• The Pitfall: Trying to increment a count for a key that does not exist in the map yet, causing null pointer references or NaN errors.
• The Solution: Always utilize fallback accessors: counts[char] = counts.get(char, 0) + 1 in Python/Java, or check membership before updating: counts.set(char, (counts.get(char) || 0) + 1) in TS/JS.

---

Practice Problems & Website Verifications

Verify your frequency counter implementations with these interactive challenges:

• Valid Anagram — Standard element count matching.
• Two Sum — Single pass dictionary index caching.
• Group Anagrams — Count array signature mapping.
• Top K Frequent Elements — Frequency counting with bucket-sort distribution.