Frequency Map Pattern

Why this pattern matters for LeetCode

Beginners often sort both strings and compare them to check for anagrams. That is O(n log n) and creates extra strings in memory. A Frequency Map counts each character once and then compares the counts — O(n) time with no sorting needed. The fundamental insight is that two strings are anagrams if and only if they have exactly the same character counts. You don't need to know the order.

What the Frequency Map pattern is

A frequency map is a hash map where the keys are values from your input and the values are counts. Build it by looping once and incrementing a counter for each element. To check if two collections match, build the frequency from one, then decrement using the other. If any counter goes to zero or below during decrement, the counts don't match. Simpler than sorting, faster in theory, and more flexible.

Reach for Frequency Map when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Frequency Map

• ✓Checking if two strings are anagrams or permutations of each other
• ✓Finding all anagram substrings inside a larger string
• ✓Counting the most or least frequent elements (Top K Frequent)
• ✓Comparing two arrays for same-element membership regardless of order
• ✓Any problem that needs character or element tallies

When NOT to use Frequency Map

• ✕You only need to know if an element appeared at all — a Set is simpler
• ✕You need to store non-count data alongside each key — use a hash Map
• ✕The input is already sorted and you want O(1) space — a two-pointer comparison may work
• ✕The alphabet is bounded and small — a fixed-size 26-element array may be cleaner than an object

Better alternative: In those cases, a Set for existence checks or a plain sorted comparison may be more readable.

JavaScript code template

Valid Anagram core pattern — O(n) time, O(k) space

if (s.length !== t.length) return false;

const count = {};

// Build frequency for s
for (const char of s) {
  count[char] = (count[char] ?? 0) + 1;
}

// Consume frequency with t
for (const char of t) {
  if (!count[char]) return false; // missing or already depleted
  count[char]--;
}

return true;

First check lengths — if they differ, they can't be anagrams. Then count every character in s. Then walk t and decrement. If t has a character that s didn't have (or had fewer of), count[char] will be 0 or undefined and you return false immediately. If you finish t without hitting a zero, the counts matched perfectly.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Check if the lengths of the two inputs are equal — if not, return false immediately.
2. 2Loop through the first input and build a frequency map: increment count[char] for each character.
3. 3Loop through the second input and decrement: count[char]-- for each character.
4. 4Before decrementing, check that count[char] is truthy — if it's 0 or undefined, return false.
5. 5If you make it through both loops, the frequency maps matched — return true.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Valid Anagram

  Count each character in both strings and compare the tallies to determine if one is a rearrangement of the other.

  Free→
• Group Anagrams

  Group strings by their sorted character count or frequency signature as the map key.

  Premium→
• Find All Anagrams in a String

  Sliding window with a frequency map — slide a window of size p.length and compare counts.

  Premium→
• Top K Frequent Elements

  Build a frequency map then extract the top k entries by count.

  Premium→
• Ransom Note

  Count available letters from the magazine, then check if the ransom note's letters can be covered.

  Premium→
• First Unique Character in a String

  Build a frequency map, then scan for the first character with count === 1.

  Premium→

Common mistakes beginners make

• ✕Sorting both strings to compare — works, but O(n log n) when O(n) is available with a frequency map.
• ✕Using a Set instead of a map — a Set only tells you a character exists, not how many times it appears.
• ✕Not checking string lengths first — 'ab' and 'abc' will pass a naive frequency check if you only count from one side.
• ✕Decrementing into negative without catching it — always check that count[char] is truthy before decrementing.

Frequency Map vs Set vs Hash Map

Choose the right tool for the job.

Time and space complexity

Two passes through the input (one to build, one to consume) each take O(n). The frequency map stores at most k unique characters — for lowercase English letters, k is at most 26, making this effectively O(1) space. For arbitrary Unicode, k can be up to n in the worst case.

Frequently asked questions

Why is a Frequency Map better than sorting for anagram checks?

Sorting is O(n log n). A frequency map is O(n). For large strings, that difference matters. Sorting also creates new strings in memory. The frequency map approach is faster and uses only O(k) space where k is the alphabet size.

Why does Valid Anagram use a Frequency Map instead of a Set?

Because a Set only records whether a character appeared — not how many times. 'aab' and 'ab' have the same unique characters but different counts, so they're not anagrams. You need the count, which is why you use a frequency map.

What's the difference between a Frequency Map and a regular Set?

A Set answers 'did I see this value?' A Frequency Map answers 'how many times did I see this value?' Use a Set when existence is all you need. Use a Frequency Map when the count matters.

Is the Frequency Map approach really O(n)?

Yes. You loop through s once (O(n)) to build the map, then through t once (O(n)) to decrement. Each character access and update is O(1). Total: O(n). The map itself stores at most 26 keys for lowercase English letters, which is constant space.