Hash Map Patterns for Coding Interviews: The Essential Guide

Example 1 — Two Sum (LC 1)

Given an array of integers nums and a target, return the indices of the two numbers that add up to the target. Each input has exactly one solution.

Approach: Iterate through the array. For each element, compute the complement (target − current). If the complement exists in our hash map, return both indices. Otherwise, store {current_value: index}.

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

# Walkthrough with nums = [2, 7, 11, 15], target = 9
# i=0: complement = 9-2 = 7, seen={} → not found → seen={2:0}
# i=1: complement = 9-7 = 2, seen={2:0} → FOUND → return [0, 1]

Time: O(n) — single pass. Space: O(n) — hash map stores at most n entries.

Example 2 — Group Anagrams (LC 49)

Given a list of strings, group the anagrams together. Two strings are anagrams if they contain the same characters in different order.

Key insight: Anagrams share the same sorted character sequence. Use the sorted string as the hash map key and append each original string to the corresponding bucket.

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # canonical form
        groups[key].append(s)
    return list(groups.values())

# Input:  ["eat", "tea", "tan", "ate", "nat", "bat"]
# Keys:   ('a','e','t') → ["eat","tea","ate"]
#         ('a','n','t') → ["tan","nat"]
#         ('a','b','t') → ["bat"]

Time: O(n · k log k) where k is the max string length. Space: O(n · k).

Optimization: Instead of sorting, use a 26-element count tuple as the key for O(n · k) time — useful when strings are very long.

Example 3 — Subarray Sum Equals K (LC 560)

Given an integer array and a target k, return the total number of continuous subarrays whose sum equals k. The array may contain negative numbers, so sliding window alone will not work.

Key insight: Use the prefix sum + hash map combo. If prefix[j] − prefix[i] = k, the subarray from i+1 to j sums to k. Store prefix sum frequencies in a hash map and look up (current_prefix − k) at each step.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    prefix_counts = {0: 1}  # base case: empty prefix

    for num in nums:
        prefix += num
        # How many earlier prefixes satisfy prefix - earlier = k?
        count += prefix_counts.get(prefix - k, 0)
        prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1

    return count

# Walkthrough with nums = [1, 2, 3], k = 3
# prefix=1: look up 1-3=-2 → 0. Store {0:1, 1:1}
# prefix=3: look up 3-3= 0 → 1. count=1. Store {0:1, 1:1, 3:1}
# prefix=6: look up 6-3= 3 → 1. count=2. Store {0:1, 1:1, 3:1, 6:1}
# Answer: 2 → subarrays [1,2] and [3]

Time: O(n). Space: O(n). This prefix sum + hash map combo is one of the most versatile techniques in competitive programming and interviews.