Hash Map Pattern: Template + 709 LeetCode Problems

What the hash map pattern is

A hash map converts a search into a lookup, which is why it is the most common single answer in this entire corpus — 588 of the 3000 problems are built on one. Three uses cover nearly all of them. The complement lookup asks, at each element, whether the thing that would complete the answer has already been seen: storing values as you go turns two nested loops into one pass, and the reason it works is that a pair is found from its second member, so only the past needs to be remembered. Frequency counting answers anagram, majority and top-k questions by comparing counts instead of arrangements. Grouping needs a canonical key — a sorted string, a character-count tuple, a normalised pattern — chosen so that two inputs collide exactly when they belong together, and that choice is the whole problem. Python's dict preserves insertion order, so an ordered result often needs no extra bookkeeping.

When to use it

• —The brute force is a nested loop asking "is there another element such that…".
• —You are counting occurrences, or comparing two multisets.
• —Items must be grouped by a property you can compute into a stable key.
• —Membership must be tested repeatedly and the input is not sorted.
• —Seen-before state has to survive across a single pass — de-duplication, cycle detection on values.

The hash map template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 709 problems listed below.

def two_sum(nums, target):
    seen = {}                            # value -> the index it was found at

    for i, value in enumerate(nums):
        if target - value in seen:       # the partner was already scanned
            return [seen[target - value], i]
        seen[value] = i

    return []

Complexity characteristics

Time

O(1) average per operation, O(n) worst case

Auxiliary space

O(n)

Average-case constant lookups are what turn a nested-loop search into a single pass, so the complement and frequency-counting solutions are O(n) time and O(n) space. The worst case is linear per operation when every key collides, which is irrelevant on real data and is the reason a language's string hash is randomised per process. Ordering is not free: getting a sorted result out of a map costs the sort on top.

All 709 hash map LeetCode problems

Every problem in the library the hash map pattern applies to, grouped by LeetCode's own difficulty rating. 601 of the 709 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Hash Map pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.