Why Hash Maps Are Fundamental
Hash maps (dictionaries in Python, HashMaps in Java) provide O(1) average-case lookup, insertion, and deletion. They are the most frequently used data structure in coding interviews after arrays and strings. Mastering hash map patterns transforms O(n²) brute-force solutions into O(n) optimal ones. Nearly every frequency counting, lookup optimization, or complement-finding problem uses a hash map.
Two Sum Pattern (Complement Lookup)
The canonical example: given an array, find two elements that sum to a target. Brute force: O(n²). Hash map: O(n).
def twoSum(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
For each element, check if its complement was already seen — if yes, found the pair. If no, store it for future elements. Generalizations: Three Sum → fix one element, apply two-sum on the remaining array. Four Sum → fix two elements, apply two-sum.
Frequency Counting
Count occurrences of each element: defaultdict(int) or Counter. Applications:
- Valid Anagram: count character frequencies in both strings, compare maps. O(n).
- Group Anagrams: sort each string as a key; group strings with the same key. O(n × k log k) where k = max string length.
- Top K Frequent Elements: count frequencies, then heap of size k, or bucket sort by frequency (O(n)).
- Majority Element: Boyer-Moore voting is O(1) space, but frequency map is O(n) and more intuitive.
- Subarray Sum Equals K (LC 560): prefix sums + frequency map. prefix_count[prefix_sum – k] gives the number of subarrays ending at current index that sum to k.
Prefix Sum + Hash Map
A prefix sum array enables range sum queries in O(1). Combined with a hash map, it finds subarrays with specific sum properties in O(n).
def subarraySum(nums, k):
count = 0
prefix_sum = 0
prefix_count = {0: 1} # empty subarray has sum 0
for num in nums:
prefix_sum += num
count += prefix_count.get(prefix_sum - k, 0)
prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
return count
Key insight: subarray sum from index i to j = prefix_sum[j] – prefix_sum[i-1]. If we want this to equal k, then prefix_sum[i-1] = prefix_sum[j] – k. For each prefix_sum[j], count how many previous prefix sums equal prefix_sum[j] – k.
Sliding Window with Hash Map
Variable-size sliding window problems often use a hash map to track the window’s state. Pattern: expand the right pointer; shrink the left pointer when the window violates the constraint.
Longest Substring Without Repeating Characters: hash map stores last seen index of each character. When a character is repeated, advance left pointer to max(left, last_seen[char] + 1). Window size = right – left + 1.
Minimum Window Substring (LC 76): hash map tracks character counts in the window and the target. Expand right until all target characters are covered; shrink left to minimize the window while keeping it valid.
Fruit Into Baskets (LC 904): longest subarray with at most 2 distinct values — sliding window with a frequency map. When distinct count > 2, shrink left until distinct count ≤ 2.
Counting Pairs / Difference
K-diff Pairs in an Array (LC 532): count pairs with absolute difference k. For k=0: find duplicates using frequency count. For k>0: for each num, check if (num + k) is in the hash set.
Find All Anagrams in a String (LC 438): fixed-size sliding window with character frequency comparison. Maintain a window frequency map; compare against pattern frequency map using a “match count” variable instead of dict comparison each step.
Hashing for Grouping
Group Anagrams (LC 49): key = tuple(sorted(word)). All anagrams have the same sorted representation → same key → same group.
Isomorphic Strings (LC 205): maintain two maps (s→t char mapping and t→s mapping). A bijection must exist — check both directions.
Word Pattern (LC 290): same pattern as isomorphic strings but mapping words to letters.
LRU Cache (LC 146): hash map (key → doubly linked list node) + doubly linked list (maintains access order). Hash map enables O(1) get; doubly linked list enables O(1) move to front on access and O(1) eviction from back.
Interview Tips
- When you need O(1) lookup of “have I seen X before” → hash set (not hash map — simpler)
- When you need to store a value associated with each seen element → hash map
- For complement problems: store elements seen so far, check complement on each new element
- For frequency problems: Counter(arr) gives a dict of frequencies in one line
- Prefix sum + hash map = O(n) for most “subarray with property X” problems
- defaultdict(int) avoids KeyError on increment; Counter has most_common() for top-K
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How does the Two Sum hash map solution work and why is it O(n)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Two Sum problem asks for indices of two numbers that sum to a target. Brute force checks all pairs in O(nu00b2). The hash map solution runs in O(n) with O(n) space. For each element nums[i], compute complement = target – nums[i]. If complement is already in the hash map (was seen at a previous index), return [seen[complement], i] u2014 these two indices sum to target. Otherwise, store nums[i] u2192 i in the hash map for future lookups. The hash map lookup (complement in seen) is O(1) average. Since we process each element once, total time is O(n). Why this works: we need nums[i] + nums[j] = target. Equivalently, nums[j] = target – nums[i]. For each nums[i], we ask “has its complement (target – nums[i]) appeared at some earlier index?” The hash map answers this in O(1). Key implementation detail: store the index as the value (not just True) so we can return both indices. Store nums[i] after checking for complement to avoid using the same element twice (though for Two Sum this isn’t possible since target u2260 2u00d7num unless the element appears twice).”
}
},
{
“@type”: “Question”,
“name”: “How do you solve Subarray Sum Equals K using prefix sums and a hash map?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Subarray Sum Equals K (LC 560) counts subarrays with sum = k in O(n). Brute force is O(nu00b2). Key insight: sum of subarray [i+1, j] = prefix_sum[j] – prefix_sum[i]. We want prefix_sum[j] – prefix_sum[i] = k, so prefix_sum[i] = prefix_sum[j] – k. For each position j (as we scan left to right), count how many previous prefix sums equal (current_prefix_sum – k). Maintain a hash map prefix_count where prefix_count[s] = number of times prefix sum s has been seen. Initialize prefix_count = {0: 1} (empty prefix has sum 0, with count 1 u2014 handles subarrays starting from index 0). For each element: prefix_sum += num; count += prefix_count.get(prefix_sum – k, 0); prefix_count[prefix_sum] += 1. The {0: 1} initialization handles the case where a subarray starting from index 0 sums to k u2014 prefix_sum[j] – k = 0, and we correctly count the empty prefix once. This pattern generalizes: for “number of subarrays with property X on their sum,” reformulate as “how many previous prefix sums satisfy condition C?” and use a hash map to count them.”
}
},
{
“@type”: “Question”,
“name”: “When should you use a hash set versus a hash map in interview problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a hash set (set in Python, HashSet in Java) when you only need to answer “have I seen X before?” without associating any value with X. O(1) membership test, lower memory than a hash map (no value storage). Examples: detecting duplicates (add to set, return True if already present), finding the first non-repeating element (two-pass u2014 first pass builds frequency set, second finds first with count 1 u2014 though Counter is better here), cycle detection in a sequence (store visited states), and Two Sum variant where you just need existence not the index. Use a hash map (dict in Python, HashMap in Java) when you need to store information associated with each key u2014 not just presence. Examples: Two Sum (store value u2192 index to return indices), frequency counting (value u2192 count), memoization in recursion (arguments u2192 result), LRU Cache (key u2192 node in doubly linked list), grouping (key u2192 list of elements). Rule of thumb: if you only check “is X present?” u2192 set. If you store “what is associated with X?” u2192 map. Many problems start with “track which elements you’ve seen” u2192 set, but then evolve to “track the first/last index where each element appeared” u2192 map.”
}
}
]
}