This is the written companion to the video above. All three hash map patterns are collected here so you can copy the code, study it at your own pace, or refer back without scrubbing through the video.
Pattern 1: Complement Lookup
Two Sum: O(n) time, O(n) space
Instead of checking every pair, store each value you’ve seen and look up whether the complement already exists.
def two_sum(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
return []Pattern 2: Grouping by Shared Property
Group Anagrams: O(n · k log k) time, O(n · k) space
Sort each word to produce a canonical key. Words that are anagrams produce the same key and land in the same bucket.
def group_anagrams(strs):
anagram_map = defaultdict(list)
for word in strs:
key = tuple(sorted(word))
anagram_map[key].append(word)
return list(anagram_map.values())Pattern 3: Grouping by Shared Property (Optimized Key)
Group Anagrams (character frequency): O(n · k) time, O(n · k) space
Skip the sort. Count character frequencies instead and use that count array as the key — drops the log k factor.
def group_anagrams_optimized(strs):
anagram_map = defaultdict(list)
for word in strs:
count = [0] * 26
for char in word:
count[ord(char) - ord('a')] += 1
anagram_map[tuple(count)].append(word)
return list(anagram_map.values())Full walkthrough with trace-throughs in the video above. Subscribe to the channel for more patterns like this.