Frequency Counting with Maps

Frequency counting is the single most reusable pattern this course covers: it shows up disguised as anagram detection, "find the most common tag," "does this list have duplicates," and dozens of other-sounding problems that are all, underneath, the same one-pass counting technique.

The pattern, in five lines

function countFrequencies(items) {
  const counts = new Map();
  for (const item of items) {
    counts.set(item, (counts.get(item) ?? 0) + 1);
  }
  return counts;
}

One pass over items. For each one, look up its current count (?? 0 if it's the first time seen), add one, write it back. O(n) time for n items, and O(k) auxiliary space where k is the number of distinct items — which can be far smaller than n when there's a lot of repetition, and is at most n when every item is unique.

Anagram detection: sorting versus counting

The textbook way to check if two strings are anagrams is to sort both and compare:

function isAnagramSorted(a, b) {
  const normalize = (s) => s.toLowerCase().split("").sort().join("");
  return normalize(a) === normalize(b);
}

This works, but sorting is O(n log n) — proven properly in a later lesson on sorting, but take it as given for now. A frequency-map version does better:

function isAnagramCounted(a, b) {
  if (a.length !== b.length) return false; // different lengths can never match
 
  const counts = new Map();
  for (const char of a.toLowerCase()) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }
  for (const char of b.toLowerCase()) {
    const current = counts.get(char);
    if (!current) return false; // char not in a, or already fully used up
    counts.set(char, current - 1);
  }
 
  return true; // every character in b was matched and consumed from a's counts
}

Build a's frequency map in one pass — O(n). Then walk b, decrementing counts as characters are matched and bailing immediately if a character is missing or over-used — another O(n) pass. Two sequential O(n) passes are still O(n) overall (2n simplifies to n, same as the frequency-counting lesson's general shape). That's a genuine improvement over O(n log n) — not a constant-factor tweak, an actual jump to a better growth class.

Finding the most common value

function mostCommon(items) {
  const counts = countFrequencies(items);
  let best = null;
  let bestCount = 0;
 
  for (const [item, count] of counts) {
    if (count > bestCount) {
      best = item;
      bestCount = count;
    }
  }
 
  return best;
}

Building the map is O(n). Scanning the map for the maximum is O(k) — bounded by the map's own size, itself at most n. Two sequential linear-ish passes, still O(n) overall. This exact shape — "count everything, then scan the counts for the answer" — is the one to recognize behind "most-used tag in this list," "most frequent error code in this log," "mode of a dataset."

When you only need presence, not counts: reach for Set

Not every version of this problem needs a count. "Does this array have any duplicates at all" only needs to know whether something has been seen before:

function hasDuplicates(items) {
  const seen = new Set();
  for (const item of items) {
    if (seen.has(item)) return true; // seen it before — duplicate found
    seen.add(item);
  }
  return false;
}

Same O(n) win over the nested-loop "compare every pair" alternative (O(n²)), but leaner than a full frequency Map because there's no count to maintain — just presence. Reach for Set when the question is "have I seen this," and Map when the question is "how many times."

What to remember

• Frequency counting with a Map is a single O(n) pass; the map's size is bounded by the number of distinct items, which can be much smaller than n.
• Comparing frequency maps for an anagram check is O(n), a genuine improvement over the O(n log n) sort-and-compare approach.
• "Build counts, then scan the counts for an answer" is two sequential linear passes, which is still O(n) overall — this is the shape behind "most common value" and similar problems.
• When you only need to know whether something has been seen before (not how many times), a Set is the leaner, equally O(n) tool — save Map for when you actually need the count.