Hash Map Patterns for Coding Interviews

Most brute force solutions are slow because they search for something. Scan the array to find a match. Loop through again to count occurrences. Check every pair to see if two numbers add up to a target. All of that searching is O(n) per query, and when you do it n times, you end up at O(n^2).

Hash maps fix this by turning lookups into O(1) operations. You trade a bit of memory for a massive speedup. And once you learn the three main patterns, you will start recognizing them in a huge chunk of interview problems.

Why O(1) lookup changes everything

An array lets you access elements by index in O(1) time, but finding a specific value requires scanning the whole thing. A hash map lets you look up values by key in O(1) average time. That single capability unlocks three patterns that show up constantly.

The three patterns are:

1. Frequency counting - how many times does each element appear?
2. Complement lookup - have I already seen the value I need?
3. Grouping - which elements belong together?

Every hash map interview problem is one of these three, or a combination. Learn them as building blocks and you can assemble solutions on the fly.

Pattern 1: Frequency counting

This is the simplest and most common. You walk through a collection and count how many times each element appears.

The code is almost always the same:

from collections import Counter

def frequency_count(arr):
    counts = Counter(arr)
    # or manually:
    counts = {}
    for item in arr:
        counts[item] = counts.get(item, 0) + 1
    return counts

This runs in O(n) time and O(n) space. One pass through the data, one dictionary to hold the counts.

Where it shows up:

• Valid anagram: count character frequencies in both strings and compare
• Top K frequent elements: count frequencies, then pick the K largest
• First unique character: count frequencies, then find the first with count 1
• Ransom note: count available characters and check if the note's needs are met

Here is a concrete example. Checking if two strings are anagrams:

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)

That is the entire solution. Two O(n) passes to build the counters, one O(k) comparison where k is the number of unique characters. Compare that to the brute force of sorting both strings (O(n log n)) or checking every permutation.

Pattern 2: Complement lookup (the two-sum trick)

This is the pattern behind the most famous interview question of all time: two-sum. The idea is simple. Instead of checking every pair of elements, you store what you have already seen and check whether the complement you need exists.

For two-sum with target 9: when you see the number 2, you know you need a 7. So you check your map for 7. If it is not there, store 2 and its index. When you later encounter 7, you check the map for 2, and there it is.

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

One pass. O(n) time, O(n) space. The brute force version with nested loops is O(n^2). The sorted-array-with-two-pointers version is O(n log n) due to sorting. The hash map version wins.

The complement lookup pattern works anywhere you can frame the problem as: "I have value X, do I need value Y, and have I seen Y before?"

Variations:

• Two-sum: complement = target - current
• Pair with given difference: complement = current + k or current - k
• Subarray sum equals K: use a prefix sum map where complement = prefix_sum - k
• Continuous subarray sum: similar prefix sum approach, but check divisibility

The prefix sum variant deserves its own example because it is a common interview curveball:

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}  # empty prefix sum occurs once

    for num in nums:
        prefix += num
        complement = prefix - k
        if complement in seen:
            count += seen[complement]
        seen[prefix] = seen.get(prefix, 0) + 1

    return count

This counts how many subarrays sum to exactly k. Without the hash map, you would need O(n^2) to check every subarray. With it, one pass.

Pattern 3: Grouping

Sometimes you need to bucket elements by some shared property. Hash maps are perfect for this because you can use any hashable value as a key.

The classic example is grouping anagrams. Given ["eat", "tea", "tan", "ate", "nat", "bat"], group words that are anagrams of each other.

The trick: two strings are anagrams if they have the same characters in the same quantities. Sort the characters and you get a canonical key. All anagrams sort to the same string.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

"eat", "tea", and "ate" all sort to ('a', 'e', 't'), so they land in the same bucket. One pass through the input, O(n * k log k) total where k is the max string length.

Other grouping problems:

• Group shifted strings: normalize each string relative to its first character
• Find duplicate subtrees: serialize each subtree and group by the serialized form
• Accounts merge: group accounts by email using union-find or DFS, but the initial mapping uses a hash map

When to use which pattern

If you are ever stuck on an array or string problem, ask yourself: "Would it help to remember what I have already seen?" If yes, you probably want a hash map.

Common mistakes

These are the bugs I see most often with hash map solutions.

1. Forgetting to handle the "not found" case.

When you look up a key that might not exist, you need a fallback. In Python, accessing dict[key] throws a KeyError if the key is missing. Use dict.get(key, default) or defaultdict instead.

2. Using an unhashable type as a key.

Lists are not hashable in Python, so you cannot use them as dictionary keys. Convert to a tuple first. This comes up in grouping problems where your key is a sorted list of characters.

3. Off-by-one with complement lookup.

In two-sum, make sure you check for the complement before adding the current element to the map. Otherwise, an element might match with itself. For example, with target 6 and the number 3, you do not want to return [i, i].

4. Not initializing the prefix sum map.

For subarray sum problems, you need to seed your map with {0: 1} (the empty prefix). Without this, you will miss subarrays that start at index 0.

5. Confusing "store index" vs "store count."

Two-sum needs the index (so you can return the positions). Frequency problems need the count. Subarray sum needs the count of how many times each prefix sum appeared. Using the wrong value type is an easy mistake when you are pattern-matching too quickly.

How to recognize hash map problems in interviews

Look for these signals:

• The problem involves finding or matching elements in an unsorted collection
• You need to count occurrences or check frequencies
• The brute force involves nested loops where the inner loop is just searching for something
• The problem mentions pairs, complements, or targets
• You need to group elements by some computed property
• The constraint is tight enough that O(n^2) will not pass, but O(n) will

If the data is sorted, you might not need a hash map at all. Sorted data opens up binary search and two-pointer approaches that use O(1) space. Hash maps shine on unsorted data where you need fast lookups without sorting first.

Problems to practice

Start with these. They cover all three patterns and range from easy to medium:

• Two Sum: complement lookup (the classic)
• Valid Anagram: frequency counting
• Group Anagrams: grouping
• Top K Frequent Elements: frequency counting + heap or bucket sort
• Subarray Sum Equals K: complement lookup + prefix sum
• Contains Duplicate: simplest hash set problem
• Longest Consecutive Sequence: hash set + clever iteration
• Ransom Note: frequency counting with a twist

Building blocks, not individual solutions

Here is the thing about hash map problems: once you have internalized the three core patterns, new problems stop feeling new. You see "find a pair that sums to X" and your brain immediately goes to complement lookup. You see "count the frequency of" and you reach for a Counter. You see "group these by" and you know you need a canonical key.

That is the building block approach. You are not memorizing 50 different solutions. You are learning 3 patterns that combine and recombine across dozens of problems.

Related posts

• The Two Pointers Pattern - When the data is sorted, two pointers can replace hash maps with O(1) space
• The Sliding Window Pattern - Frequency maps and counters are the backbone of most sliding window state tracking
• Stack-Based Patterns - Another core pattern family that pairs well with hash maps in many interview problems

But knowing the patterns is not the same as being able to write the code under pressure. Recognition fades. The first time you solve two-sum with a hash map, it feels obvious. Three weeks later, you might stare at a similar problem and blank on the approach. That is just how memory works.

Spaced repetition fixes this. You drill each pattern at increasing intervals until the code flows automatically. First after a day, then three days, then a week. Each time you type the solution from scratch, not just re-read it. After a few cycles, the pattern is locked in.

---

New to algorithms? Learn why hash maps give O(1) lookups with our Big O Notation Guide.