Valid Anagram — the frequency count pattern

Day 4 taught you the hash set pattern: “have I seen this before?” → O(1) membership check. Today we level up to the hash map pattern: “how many times does this appear?” → O(1) count update. Same hash-based family, different question.

The problem

Input:  s = "anagram", t = "nagaram"
Output: true  (same letters, same counts)

Input:  s = "rat", t = "car"
Output: false (different letters)

An anagram is a rearrangement. Same ingredients, different order. The question: do these two strings have the same character counts?

Approach 1: Sort both, compare — O(n log n)

The obvious approach: sort both strings. If they’re anagrams, the sorted versions will be identical.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  return s.split("").sort().join("") === t.split("").sort().join("");
}

Clean and readable. But sorting is O(n log n) time and O(n) space — split("") creates an O(n) array, and the sort itself uses O(n) auxiliary memory. You’re doing more work and using more memory than necessary. You don’t need the strings ordered; you just need to know if the counts match.

Approach 2: Hash map frequency count — O(n)

Instead of sorting, count the characters. Walk through s, incrementing a count for each character. Then walk through t, decrementing. If all counts hit zero, it’s an anagram.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const c of s) count.set(c, (count.get(c) || 0) + 1);
  for (const c of t) {
    if (!count.has(c)) return false;
    count.set(c, count.get(c) - 1);
    if (count.get(c) < 0) return false;  // more of this char in t than s
  }
  return true;
}

Two passes, O(1) work per character. That’s O(n) time. The hash map stores up to (alphabet size) entries — O(k) space where k is the number of distinct characters.

Approach 3: Fixed array — O(n), O(1) space

Here’s the optimization most candidates miss. If the alphabet is fixed (26 lowercase letters), you don’t need a hash map at all — use an array of 26 integers, indexed by character code.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (const c of s) count[c.charCodeAt(0) - 97]++;
  for (const c of t) {
    const i = c.charCodeAt(0) - 97;
    count[i]--;
    if (count[i] < 0) return false;
  }
  return true;
}

Same O(n) time, but O(1) space — the array is always 26 integers, regardless of input size. And no hashing overhead: array indexing is direct memory access.

The real benchmark

I ran all three approaches on strings of increasing size (30 iterations each, median):

Three key observations from the benchmark:

• At small n, sort can win. At n=1,000, sort (0.12ms) beats hash map (0.24ms). V8’s sort is native C; the hash map has JS-level overhead. Big O describes asymptotic growth — at small n, constant factors dominate.
• At scale, O(n) beats O(n log n). At n=1,000,000, sort (161ms) is 2.5× slower than hash map (65ms). The gap grows with n.
• Same Big O, different constants. Hash map (65ms) and fixed array (15ms) are both O(n), but the array is 4.3× faster at n=1M. Array indexing is direct memory access; hash map has hashing overhead. And the array uses O(1) space vs O(k) for the map.

The pattern: “count and compare”

When you need to compare the composition of two collections (same characters? same word counts?), use a hash map to count frequencies, then compare. O(n) time, O(k) space.

If the keyspace is bounded (26 letters, 10 digits, fixed enum), replace the hash map with a fixed array — same O(n) time, O(1) space, lower constant.

This pattern appears in: Group Anagrams (count each string’s character frequencies, use as a key), Top K Frequent Elements (count frequencies, then select the top k), Ransom Note (count magazine letters, subtract ransom letters). Once you internalize “count and compare,” these all become two-pass solutions.

The transfer question

From Day 4 → Day 5: When would you use a hash set vs a hash map? What’s the question each one answers?

Answer (click to reveal)

Use a hash set when the question is binary: “is this value present?” — you only need membership, not quantity. Example: Contains Duplicate (Day 4) — you only need to know “have I seen 1 before?”, not “how many 1s?”

Use a hash map when the question is quantitative: “how many times does this appear?” — you need a count per key. Example: Valid Anagram (Day 5) — you need to know “are there 3 a’s in both strings?”, not just “is a present?”

The rule of thumb: if you’re writing if (seen.has(x)), use a set. If you’re writing count.set(x, count.get(x) + 1), use a map.

Check your understanding