Patterns / Hashing & Counting

Hashing & Counting Pattern

Trade memory for time: one pass through the data builds a hash map you can then query in O(1).

What it is

The hashing pattern uses a hash map (or hash set) to remember things you have already seen, so that a question which naively needs a nested rescan becomes a single linear pass. The map stores a value mapped to a count, an index, or a boolean "seen" flag. Whenever a brute-force solution says "for each element, look back at all the others", a hash map usually collapses that inner loop into a constant-time lookup.

When to use it — the signals

"How many times does X occur" or frequency counts.
"Find a pair / two items that satisfy a relationship" (e.g. sum to a target).
Detecting duplicates, or "first unique" element.
Grouping items by a derived key (anagrams, categories).

How it works

A representative implementation in Java:

// Two Sum: indices of the pair summing to target — one pass, O(n).
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) return new int[]{ seen.get(need), i };
    seen.put(nums[i], i);
}
return new int[]{ -1, -1 };

Complexity

O(n) time and O(n) space in the typical case — each element is inserted and looked up once.

Common pitfalls

Forgetting that hashing trades space for speed — on memory-tight problems it may not be allowed.
Mutating the map while iterating it.
Using objects without proper equals()/hashCode(), so lookups silently miss.

Practice problems

Classic problems where this pattern is the intended approach: Two Sum, Group Anagrams, Contains Duplicate, Top K Frequent Elements. Work through them on the Leet Study home page.

← All patterns