PATTERN 1 OF 22

Hash Maps

Use hash maps for O(1) lookups to solve problems involving pairs, frequencies, grouping, or caching computed results.

Time: O(n)

Space: O(n)

Learn & Reference

Understanding the Pattern

Hash Map Pattern

Hash maps (dictionaries in Python, objects/Maps in JavaScript) provide O(1) average-case lookup, insertion, and deletion. This makes them the go-to data structure when you need to quickly find, store, or count data.

Core Concept

A hash map stores key-value pairs. Given a key, you can:

Insert a value in O(1)
Lookup a value in O(1)
Delete a value in O(1)

The hash function converts the key into an array index. Collisions are handled via chaining or open addressing.

The 4 Hash Map Archetypes

1. Complement / Pair Finding

Store seen values and check if a complement exists. This turns an O(n²) nested loop into a single O(n) pass.

2. Frequency Counting

Count occurrences of elements. Essential for "most frequent", "find duplicates", and anagram problems.

3. Grouping / Bucketing

Group elements by a shared property (anagram signature, remainder, etc.).

4. Caching / Memoization

Store computed results to avoid recalculation.

Time & Space Complexity

Time: O(n) typical — single pass through data
Space: O(n) for the hash map

When Hash Map Fails

When you need sorted order (use BST or sorted array)
When space is extremely limited (O(1) space requirement)
When keys aren't hashable (lists in Python — convert to tuples)
When you need range queries (use a sorted structure)

Common Mistakes

Using the same element twice: Add to map AFTER checking, not before
Returning values instead of indices: Read the problem carefully
Forgetting about negative numbers: Hash maps handle negatives fine
Using wrong key type: In Python, lists aren't hashable — use tuples
Not handling empty input: Always consider edge cases

When to Use

Find two numbers that sum to X

Check if a duplicate exists

Count frequency of elements

Find first non-repeating character

Group anagrams together

Two Sum variants

Problems mentioning O(1) lookup requirement

In one pass or single traversal hints

Subarray sum equals K (prefix sum + hash map)

Any problem where brute force uses nested loops to search

Template

1# --- Complement Finding (Two Sum) ---
2def two_sum(nums, target):
3    seen = {}
4    for i, num in enumerate(nums):
5        complement = target - num
6        if complement in seen:
7            return [seen[complement], i]
8        seen[num] = i
9    return []
10
11# --- Frequency Counting ---
12def most_frequent(nums):
13    from collections import Counter
14    return Counter(nums).most_common(1)[0][0]
15
16# --- Grouping / Bucketing ---
17def group_by(items, key_fn):
18    from collections import defaultdict
19    groups = defaultdict(list)
20    for item in items:
21        groups[key_fn(item)].append(item)
22    return dict(groups)

{ }

Syntax Reference

1# === Dictionary (built-in) ===
2d = {}
3d[key] = value          # set
4val = d[key]            # get (KeyError if missing)
5val = d.get(key, 0)     # get with default
6if key in d: ...        # check existence
7del d[key]              # delete
8for k, v in d.items():  # iterate
9
10# === Counter (frequency counting) ===
11from collections import Counter
12freq = Counter([1,1,2,3])     # {1:2, 2:1, 3:1}
13freq.most_common(2)           # [(1,2), (2,1)]
14freq[missing_key]             # returns 0, not KeyError
15
16# === defaultdict (auto-initialize) ===
17from collections import defaultdict
18d = defaultdict(int)          # missing keys -> 0
19d = defaultdict(list)         # missing keys -> []
20d = defaultdict(set)          # missing keys -> set()

📋

Common Recipes

1# --- Prefix Sum + Hash Map ---
2# Count subarrays with sum = k
3def subarray_sum(nums, k):
4    count, prefix = 0, 0
5    seen = {0: 1}
6    for num in nums:
7        prefix += num
8        if prefix - k in seen:
9            count += seen[prefix - k]
10        seen[prefix] = seen.get(prefix, 0) + 1
11    return count
12
13# --- First Unique ---
14def first_unique(s):
15    freq = Counter(s)
16    for i, ch in enumerate(s):
17        if freq[ch] == 1:
18            return i
19    return -1
20
21# --- Group Anagrams ---
22def group_anagrams(strs):
23    groups = defaultdict(list)
24    for s in strs:
25        key = tuple(sorted(s))
26        groups[key].append(s)
27    return list(groups.values())

O(n)

Complexity

Operation	Average	Worst Case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
Iterate	O(n)	O(n)

Watch Out

✗When you need sorted order (use BST or sorted array)
✗When space is extremely limited (O(1) space requirement)
✗When keys aren't hashable (lists in Python — convert to tuples)
✗When you need range queries (use a sorted structure)
✗Using the same element twice: Add to map AFTER checking, not before
✗Returning values instead of indices: Read the problem carefully
✗Forgetting about negative numbers: Hash maps handle negatives fine
✗Using wrong key type: In Python, lists aren't hashable — use tuples
✗Not handling empty input: Always consider edge cases

PRACTICE PROBLEMS

Two Pointers