Hash Map Counting

Tactic

Hash map counting stores what has already appeared, how often it appeared, or where it appeared. The lookup turns a future question into a direct membership or frequency check.

The invariant is that the map represents the processed portion of the input. For complements, it answers whether the missing value has been seen. For anagrams, it represents the remaining or current character counts. For grouping, it maps a canonical key to matching items.

The design choice is the key. Sometimes the raw value is enough. Sometimes the key is a tuple, a remainder, a sorted string, or a frequency vector. Most mistakes come from choosing a key that loses information or keeps too much irrelevant information.

Value

The value is trading memory for direct access. Many quadratic comparisons become one pass because earlier values are indexed by the question the current value needs to ask.

Direct complexity example

Brute force: Compare every pair or every string against every other string: $O(n^2)$ time, or worse when each comparison scans characters.
With this tactic: Store counts or canonical keys in a map: $O(n)$ expected time for simple keys, often $O(nk)$ when each key costs k to build.
Space: The space is $O(u)$ for u distinct keys, plus any grouped output that the problem requires.

Challenges this solves

two-sum complements
frequency equality
grouping anagrams
subarray count by remainder or prefix
first unique or duplicate detection

When to use it

Use this tactic when these conditions are true:

the question asks whether a matching value has appeared
multiplicity matters
a complement or remainder defines the missing partner
sorting would work but a linear expected-time lookup is available

When not to use it

Reach for a different tactic when these warning signs appear:

the key would be as large as the whole remaining problem state
order relationships are more important than membership
hash collisions or memory limits dominate
the input domain is tiny enough for an array counter to be simpler

Terminology clues

These prompt words often point toward this concept:

frequency
count
seen before
duplicate
anagram
complement
remainder
group by