Hash Maps & Sets

Counting, complements, grouping and prefix sums.

Hash maps and sets give you O(1) average-time lookups, and that alone turns countless O(n²) brute-force solutions into O(n). If you're comparing every pair of elements, ask: *can I remember what I've already seen instead?*

When to use it

"Have I seen this before?" — duplicates, cycles, visited states
"Find a pair/complement" — two-sum style problems
Counting frequencies — anagrams, majority element, top-K
Grouping by a computed key — group anagrams, bucket by pattern
Prefix sums with a map — subarrays summing to k

Template: complement lookup

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

One pass, O(n) time, O(n) space — versus O(n²) checking every pair.

Template: counting

from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

def group_anagrams(words):
    groups = {}
    for w in words:
        key = "".join(sorted(w))  # or a 26-length count tuple for O(L)
        groups.setdefault(key, []).append(w)
    return list(groups.values())

Template: prefix sum + hash map

To count subarrays with sum k (works with negative numbers, unlike a sliding window):

def subarray_sum(nums, k):
    count, prefix = 0, 0
    seen = {0: 1}  # prefix sum -> number of times seen
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

The insight: sum(i..j) = prefix[j] - prefix[i-1], so a subarray ending here sums to k exactly when an earlier prefix equals prefix - k.

Pitfalls

Mutable keys: lists can't be dict keys in Python — convert to tuples.
Order of insert and lookup: in two-sum, check *before* inserting so an element doesn't pair with itself.
Worst-case O(n): adversarial inputs can degrade hashing; mention it only if asked.

[!TIP] Practice Subarray Sum Equals K · Top K Frequent Elements · Time-Based Key-Value Store