Hash Maps — How the Pattern Works
The Hash Map pattern indexes previously seen elements, frequencies, canonical signatures, or prefix states into an associative table backed by a deterministic hash function for O(1) average-time insert, lookup, and deletion. During a single pass, the map maintains an invariant over processed history — such as exact element counts, earliest indices of prefix sums, or bidirectional pairings — so each query resolves in constant time rather than rescanning the input. Trading O(n) auxiliary space for instant key-based retrieval collapses nested O(n^2) or O(n^3) pairwise and subarray scans down to O(n) time.
- Checking membership, deduplicating elements, or detecting the first repeated value or state cycle during a sequential scan.
- Counting element frequencies, matching multisets copy-for-copy, or rearranging elements according to an external rank order without O(n log n) comparison sorting.
- Computing subarray counts or maximum subarray lengths over prefix sums, modular remainders, or XOR parity bitmasks (especially when negative values invalidate sliding windows).
- Grouping, linking, or spellchecking items that share a normalized or translation-invariant canonical key (file contents, coordinate offsets, lowercase/devoweled forms, or boundary words).
- Enforcing a strict one-to-one bijection between two sequences or solving algebraically for a target complement (e.g., target - x or total - 2 * s) and verifying its existence in O(1) time.
- Overwriting earliest indices in longest-subarray problems (
Contiguous Array,Continuous Subarray Sum): updatingfirst[state] = ion repeats shrinks candidate subarray lengths instead of preserving the leftmost boundary; also seed{0: -1}to capture valid prefixes starting at index 0. - Inserting the current prefix sum before querying
prefix - kinSubarray Sum Equals K: whenk == 0, premature insertion matchesprefixagainst itself and falsely counts empty subarrays. - Checking only a single direction (
s -> t) in bijection problems (Isomorphic Strings,Word Pattern), which misses many-to-one collisions where two distinct source keys map to the same target value. - Passing mutable containers (
list,set,dict) as Python dictionary keys, which raisesTypeError: unhashable type; convert composite shapes or states totuple,frozenset,str, or integer bitmasks first. - Reusing the same element twice when probing a complement or algebraic target (
Identify the Largest Outlier): iftarget_val == current_val, requirecount[target_val] >= 2rather than>= 1.
def match_with_counts(source, target):
count = {}
for x in source:
count[x] = count.get(x, 0) + 1
result = []
for y in target:
if count.get(y, 0) > 0:
result.append(y)
count[y] -= 1
return resultdef count_subarrays_with_sum(nums, k):
seen = {0: 1}
prefix = count = 0
for x in nums:
prefix += x
count += seen.get(prefix - k, 0)
seen[prefix] = seen.get(prefix, 0) + 1
return countdef longest_equal_state_subarray(nums, step_fn):
first = {0: -1}
state = best = 0
for i, x in enumerate(nums):
state = step_fn(state, x)
if state in first:
best = max(best, i - first[state])
else:
first[state] = i
return bestdef is_bijection(seq_a, seq_b):
if len(seq_a) != len(seq_b):
return False
a_to_b, b_to_a = {}, {}
for a, b in zip(seq_a, seq_b):
if a_to_b.setdefault(a, b) != b or b_to_a.setdefault(b, a) != a:
return False
return Truedef group_by_canonical_key(items, key_fn):
groups = {}
for item in items:
key = key_fn(item) # Must be hashable (int, str, tuple, frozenset)
groups.setdefault(key, []).append(item)
return list(groups.values())