Recap — When to Reach for a HashMap

# When to Reach for a HashMap Hashmaps (Python dict) and hashsets (Python set) are O(1) lookup/insert/delete on average. They're the workhorse of interview problems — most O(N) solutions where brute force is O(N²) involve a hashmap. ## The mental signals Reach for a hashmap when you see: 1. **"Have I seen this before?"** → hashset 2. **"What's the count of each X?"** → hashmap (X → count) 3. **"Given X, find the corresponding Y."** → hashmap (X → Y) 4. **"Pair/group elements by some property."** → hashmap (property → list) 5. **"Find pair that sums to target."** → hashmap (complement → index) ## Canonical patterns ### Pattern 1: Existence check ```python def has_duplicate(arr): seen = set() for x in arr: if x in seen: return True seen.add(x) return False ``` Brute force: O(N²). With set: O(N). ### Pattern 2: Counter (frequency map) ```python from collections import Counter def most_common(s): counts = Counter(s) return counts.most_common(1)[0] ``` Or build it yourself: ```python counts = {} for ch in s: counts[ch] = counts.get(ch, 0) + 1 ``` ### Pattern 3: Two-sum style (complement lookup) ```python def two_sum(arr, target): seen = {} for i, x in enumerate(arr): complement = target - x if complement in seen: return [seen[complement], i] seen[x] = i return [] ``` The key insight: as you scan, ask "would I have completed the pair if I'd already seen the complement?" ### Pattern 4: Group by property ```python def group_anagrams(strs): groups = {} for s in strs: key = tuple(sorted(s)) # anagrams share this key groups.setdefault(key, []).append(s) return list(groups.values()) ``` Choose a key that captures "what makes these equivalent". The key types I see most: - `tuple(sorted(s))` for anagrams - frequency tuple for permutations - `(x, y)` for coordinate dedup - canonical form of a graph or grid pattern ### Pattern 5: Hashmap + index for "last seen position" ```python def length_of_longest_substring(s): last = {} # char → last index seen start = 0 best = 0 for i, ch in enumerate(s): if ch in last and last[ch] >= start: start = last[ch] + 1 last[ch] = i best = max(best, i - start + 1) return best ``` Combines hashmap with sliding window. Very common. ## Python idioms ### `defaultdict` ```python from collections import defaultdict groups = defaultdict(list) for item in items: groups[item.category].append(item) ``` Cleaner than `setdefault` for collecting. ### `Counter` ```python from collections import Counter c = Counter("hello") # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1}) most = c.most_common(2) # [('l', 2), ('h', 1)] diff = Counter(a) - Counter(b) # in a, not in b ``` ### `set` operations ```python common = set_a & set_b # intersection either = set_a | set_b # union only_a = set_a - set_b # difference ``` For "find common elements between two arrays": just `set(a) & set(b)`. ## The complexity story Hashmap operations are O(1) average, O(N) worst case (rare; pathological hash collisions). In interviews, you state O(1) for hashmap ops and "O(N) worst case but average is O(1) in practice." Space: O(N) extra space for the hashmap is usually acceptable. The trade is "more memory for less time." When NOT to use hashmap: - Need sorted order → use TreeMap (sorted dict) or sort separately - Memory constrained, brute force fast enough → keep it simple - Values matter, not just keys → consider arrays if domain is small ## Hashing custom objects In Python, tuples and frozensets are hashable; lists and sets are not. ```python # Hashable as key seen = set() seen.add((1, 2, 3)) # tuple — OK seen.add(frozenset([1, 2])) # frozenset — OK # NOT hashable # seen.add([1, 2, 3]) # TypeError: unhashable type: 'list' # seen.add({1, 2}) # TypeError ``` For grids/coordinates: tuple `(row, col)`. For sub-arrays as keys: convert to tuple `tuple(arr)`. ## Common mistakes 1. **Forgetting to update the hashmap.** Adding key before checking causes false positives. 2. **Using a list as a key.** Not hashable; convert to tuple. 3. **Reaching for hashmap when sort would do.** If you're hashmapping just to find duplicates and don't need indices, set is enough. 4. **Iterating dict and modifying it.** Use `list(d.keys())` first. 5. **Counter equality on different types.** `Counter("ab") == Counter(["a", "b"])` is True; can surprise. ## Takeaway Hashmap = O(1) lookup. Recognize signals: existence, count, complement, group-by, last-seen. Common combos: hashmap + sliding window (last-seen), hashmap + sort (group-by), hashmap + two pointers (rare). Trade space for time; usually worth it. Python's `dict`, `Counter`, `defaultdict`, `set` cover 95% of cases.