HashMap Tricks: 4 Interview Problems Where Dict Beats Array

HashMap Tricks: 4 Problems Where Dict Beats Array in Python

You’re 20 minutes into a coding interview. The brute force solution is working, but the interviewer just asked, “Can you do better than $O(n^2)$?” You reach for nested loops, maybe a sorted array. But the real answer is often simpler: swap your list for a dictionary.

HashMaps (Python’s dict) turn $O(n)$ searches into $O(1)$ lookups. That’s the theory. In practice, knowing when to use them separates candidates who pass from those who don’t. Here are four problems where dictionaries outperform arrays, with the exact mistakes I’d make under pressure.

Problem 1: Two Sum — The Dictionary Wake-Up Call

This is the classic. Given an array of integers and a target sum, find two numbers that add up to the target.

Most people start here:

def two_sum_brute(nums, target):
    # Check every pair
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# Test
nums = [2, 7, 11, 15]
print(two_sum_brute(nums, 9))  # [0, 1]

Time complexity: $O(n^2)$. For n=10000, that’s 100 million comparisons. The interviewer is already writing notes.

The dict trick: instead of searching the array for target - nums[i], store what you’ve seen in a HashMap. When you hit a number, check if its complement exists.

def two_sum_hash(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i  # Store current number AFTER checking
    return []

print(two_sum_hash([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum_hash([3, 2, 4], 6))      # [1, 2]

Time: $O(n)$, space: $O(n)$. One pass. The if complement in seen check is $O(1)$ average case — that’s the entire advantage.

The gotcha: I used to store seen[num] = i before the check. That breaks when target = 2 * num (e.g., nums=[3, 3], target=6). You’d find the same element twice. Storing after the check avoids this.

Problem 2: Group Anagrams — Sorting vs Counting

Given a list of strings, group anagrams together. For example, ["eat", "tea", "tan", "ate", "nat", "bat"] becomes [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

The naive approach sorts each string and uses that as a key:

from collections import defaultdict

def group_anagrams_sort(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))  # O(k log k) per string
        groups[key].append(s)
    return list(groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sort(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Time: $O(n \cdot k \log k)$ where $n$ is the number of strings and $k$ is the max string length. For short strings, this is fine. But sorting every string adds overhead.

The faster dict trick uses character counts as the key:

def group_anagrams_count(strs):
    groups = defaultdict(list)
    for s in strs:
        # Count chars: [count of 'a', count of 'b', ..., count of 'z']
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        key = tuple(count)  # Lists aren't hashable, tuples are
        groups[key].append(s)
    return list(groups.values())

print(group_anagrams_count(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Time: $O(n \cdot k)$. Counting is linear in string length, no sorting. The tuple of 26 integers is the HashMap key — (1, 0, 0, 1, 1, 0, ..., 0, 1, 0) for “eat” (counts for ‘a’, ‘e’, ‘t’).

The gotcha: I tried using key = count directly. Python dicts require hashable keys, and lists aren’t hashable. Converting to tuple(count) fixes it. Also, this only works for lowercase English letters. If the input includes uppercase or Unicode, you’d need collections.Counter instead:

from collections import Counter

def group_anagrams_counter(strs):
    groups = defaultdict(list)
    for s in strs:
        # Counter works with any characters
        key = tuple(sorted(Counter(s).items()))
        groups[key].append(s)
    return list(groups.values())

Problem 3: Longest Consecutive Sequence — $O(n)$ Without Sorting

Given an unsorted array, find the length of the longest consecutive sequence. For [100, 4, 200, 1, 3, 2], the answer is 4 (the sequence [1, 2, 3, 4]).

The obvious solution sorts the array:

def longest_consecutive_sort(nums):
    if not nums:
        return 0
    nums.sort()  # O(n log n)
    longest = 1
    current = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:  # Skip duplicates
            continue
        if nums[i] == nums[i-1] + 1:
            current += 1
        else:
            longest = max(longest, current)
            current = 1
    return max(longest, current)

print(longest_consecutive_sort([100, 4, 200, 1, 3, 2]))  # 4

Time: $O(n \log n)$. The interviewer asks, “Can you do it in linear time?”

The dict trick (well, set, but same idea) checks if each number is the start of a sequence:

def longest_consecutive_hash(nums):
    num_set = set(nums)  # O(n) to build, O(1) lookups
    longest = 0

    for num in num_set:
        # Only start counting if this is the beginning of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest = max(longest, current_streak)

    return longest

print(longest_consecutive_hash([100, 4, 200, 1, 3, 2]))  # 4
print(longest_consecutive_hash([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # 9

Time: $O(n)$. The key insight: if num - 1 not in num_set ensures we only start counting from sequence beginnings. For [1, 2, 3, 4], we start at 1, not at 2, 3, or 4. Each number is visited at most twice (once in the outer loop, once in the while loop).

The gotcha: Without the num - 1 check, this becomes $O(n^2)$ — you’d count every subsequence. That check is what makes it linear. I missed this in a mock interview once and couldn’t figure out why my “optimized” solution timed out.

Problem 4: Subarray Sum Equals K — Prefix Sums + HashMap

Given an array of integers and a target k, count how many subarrays sum to k. For nums=[1, 1, 1], k=2, the answer is 2 (subarrays [1,1] at indices 0-1 and 1-2).

Brute force checks every subarray:

def subarray_sum_brute(nums, k):
    count = 0
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            if current_sum == k:
                count += 1
    return count

print(subarray_sum_brute([1, 1, 1], 2))  # 2
print(subarray_sum_brute([1, 2, 3], 3))  # 2

Time: $O(n^2)$. For n=10000, that’s 100 million sums.

The dict trick uses prefix sums. The idea: if prefix_sum[j] - prefix_sum[i] = k, then the subarray from i+1 to j sums to k. Rearranging: prefix_sum[i] = prefix_sum[j] - k. So as we iterate, we check if we’ve seen current_sum - k before.

def subarray_sum_hash(nums, k):
    prefix_counts = {0: 1}  # prefix_sum -> how many times we've seen it
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        # Check if there's a prefix sum that would give us sum=k
        if current_sum - k in prefix_counts:
            count += prefix_counts[current_sum - k]
        # Record this prefix sum
        prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

    return count

print(subarray_sum_hash([1, 1, 1], 2))  # 2
print(subarray_sum_hash([1, 2, 3], 3))  # 2
print(subarray_sum_hash([1, -1, 0], 0))  # 3

Time: $O(n)$, space: $O(n)$. The formula $\text{subarray sum from } i+1 \text{ to } j = \text{prefix}[j] – \text{prefix}[i]$ is the core. We’re storing prefix_sum -> frequency because multiple indices can have the same prefix sum (especially with negatives or zeros).

The gotcha: Initializing prefix_counts = {0: 1} handles subarrays that start at index 0. Without it, nums=[3], k=3 would return 0 instead of 1. I debugged this for 10 minutes once before realizing I needed that seed value. Also, note prefix_counts.get(current_sum, 0) + 1 — you can’t just do += 1 on a missing key without defaultdict.

When to Reach for a HashMap

These four problems share a pattern:

1. You need fast lookups: “Have I seen this value before?” or “Does the complement exist?”
2. You’re checking membership repeatedly: $O(n)$ search in a list becomes $O(1)$ in a dict
3. You need to count or group: HashMap keys naturally deduplicate and aggregate

But dictionaries aren’t always the answer. If the input is already sorted, binary search might be simpler. If you need to maintain order, a list with indices might be clearer. And if memory is tight, the $O(n)$ space overhead of a HashMap can be a dealbreaker.

One useful detail: Python’s dict implementation (since Python 3.7, officially guaranteed) maintains insertion order. This is a result of the compact dict optimization introduced in Python 3.6. It means you can rely on iteration order matching insertion order, which occasionally simplifies interview problems where order matters.

FAQ

Q: When should I use collections.defaultdict vs a regular dict?

defaultdict saves you from checking if key in dict before incrementing or appending. Use it when you’re building frequency maps or grouping (like the anagram problem). Stick with regular dict when you need to check for key existence explicitly (like Two Sum).

Q: Are dictionary lookups always $O(1)$?

Average case yes, worst case $O(n)$ if hash collisions force a linear scan. In practice, Python’s hash function is good enough that you’ll never see $O(n)$ lookups in an interview. But if the interviewer pushes, mention that worst-case can degrade with adversarial inputs (though Python 3.3+ added randomized hashing to prevent this).

Q: Can I use a set instead of a dict if I don’t need to store values?

Absolutely. The Longest Consecutive Sequence solution uses a set because we only care about membership, not counts or indices. Sets have the same $O(1)$ lookup but use less memory. If you’re only checking “is this in here?”, prefer set over dict.

What I’d Do Differently

If I were re-doing these problems, I’d focus less on memorizing the HashMap pattern and more on asking, “What am I searching for repeatedly?” That question leads you to the optimization naturally. The Two Sum trick isn’t about knowing the solution — it’s about noticing you’re scanning the array $n$ times and wondering if there’s a faster way to check for complements.

Use a HashMap when you’re checking membership in a loop. If you’re only iterating once, a list is fine. If you need ordering, a list is better. But if you catch yourself writing if x in my_list inside a loop, that’s your cue to swap it for a dictionary.

Debugging these under time pressure taught me one thing: the hard part isn’t knowing HashMap lookups are $O(1)$. It’s recognizing which value to use as the key. In Two Sum, it’s the number itself. In Group Anagrams, it’s the character count. In Subarray Sum, it’s the prefix sum. That insight — what should I index on? — is what separates a passing solution from a time limit exceeded.

Next time you hit $O(n^2)$ in an interview, pause and ask: what am I looking up? If the answer is “a value I’ve seen before,” reach for a dict.