The frequency map pattern

Short answer. A frequency map stores each value with the number of times it appears, and one pass builds it. Reach for it when a problem asks how many times, the most frequent, duplicates, anagrams or unique items. It costs O(n) time and O(k) space for k distinct values. Delete a key when its count reaches zero.

The signals

Reach for it when a problem says any of these.

"How many times", "most frequent", "duplicate", "anagram", "unique", "at least k occurrences".

All of them ask about counts, not positions. That is the tell.

No order in the question usually means no order in the answer.

Four problems it closes

Anagrams. Two strings are anagrams when their counts match. One pass each, then compare.

O(n), and no sorting.

First non-repeating character is solved by counting in one pass. Walk the string again and return the first count of 1.

Two passes. The order comes back on the second.

Top k frequent. Count, then take the k largest counts with a heap. Counting is O(n), the heap is n log k.

Majority element. Count, then check for one above n over 2.

A clever constant-space solution exists, the Boyer-Moore vote. Write the counting version first anyway.

The array version

A small, known alphabet lets you drop the map.

Lowercase English letters is 26 slots.

An array indexed by the character code beats a hash map on speed and memory. The space becomes O(1).

Same for digits, or values bounded by 10 to the sixth. The constraints tell you which version is allowed.

Counts inside a window

The pattern gets far more useful once the counts move.

Slide a window over a string. Add the entering character, remove the leaving one.

The map now describes only the current window.

"The longest substring with at most 2 distinct characters" becomes one pass.

Alongside it you track one number. How many distinct keys are in the map.

That number is what your loop condition tests.

The bug everyone writes

When the window shrinks, you decrement a count. It reaches zero, and the key is still there.

The map now says 3 distinct characters when there are 2. The loop condition is quietly wrong.

Short tests still pass. That is the worst part.

Delete the key when its count hits zero. Every time.

Two more worth knowing.

A missing key reads as undefined, not 0. Add the default explicitly.

A plain JavaScript object stringifies its keys, so numbers and strings collide. Map does not.

What it costs

Time is O(n), one pass. Space is O(k), where k is the number of distinct values.

Say the space part out loud in an interview.

Counting looks free. On a large input it is a full extra copy of the distinct values.

Where this sits

AlgoPath puts the frequency map at step 18. Two pointers and sliding windows come next, and both lean on it.

Why a map and not an array is in set vs map vs array, and what is underneath it is in how hash tables work.

The first 33 steps are free.