Classic Map Problems
1. Two Sum
Problem: Find indices of two numbers that add to target.
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 []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
Time: O(n), Space: O(n)
2. Longest Substring Without Repeating Characters
Problem: Find length of longest substring without repeating characters.
def length_of_longest_substring(s):
char_index = {}
max_length = 0
start = 0
for end, char in enumerate(s):
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
char_index[char] = end
max_length = max(max_length, end - start + 1)
return max_length
print(length_of_longest_substring("abcabcbb")) # 3
3. Group Anagrams
Problem: Group strings that are anagrams.
from collections import defaultdict
def group_anagrams(strs):
anagrams = defaultdict(list)
for s in strs:
# Sort string as key
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
# Alternative: use character count as key
def group_anagrams_v2(strs):
anagrams = defaultdict(list)
for s in strs:
count = [0] * 26
for char in s:
count[ord(char) - ord('a')] += 1
anagrams[tuple(count)].append(s)
return list(anagrams.values())
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
4. Valid Anagram
Problem: Check if two strings are anagrams.
def is_anagram(s, t):
if len(s) != len(t):
return False
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1
for char in t:
if char not in freq or freq[char] == 0:
return False
freq[char] -= 1
return True
# Or simply:
def is_anagram_v2(s, t):
return sorted(s) == sorted(t)
print(is_anagram("anagram", "nagaram")) # True
5. Subarray Sum Equals K
Problem: Count subarrays with sum equal to k.
def subarray_sum(nums, k):
prefix_sums = {0: 1}
current_sum = 0
count = 0
for num in nums:
current_sum += num
# Check if we've seen (current_sum - k)
if current_sum - k in prefix_sums:
count += prefix_sums[current_sum - k]
prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, 2, 3], 3)) # 2
Key Insight: Use prefix sums to convert to "two sum" problem.
6. Longest Consecutive Sequence
Problem: Find longest consecutive sequence length.
def longest_consecutive(nums):
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
# Only start from sequence beginning
if num - 1 not in num_set:
current = num
length = 1
while current + 1 in num_set:
current += 1
length += 1
max_length = max(max_length, length)
return max_length
print(longest_consecutive([100, 4, 200, 1, 3, 2])) # 4
7. Top K Frequent Elements
Problem: Return k most frequent elements.
from collections import Counter
import heapq
def top_k_frequent(nums, k):
# Using Counter
freq = Counter(nums)
return [num for num, count in freq.most_common(k)]
# Using heap
def top_k_frequent_heap(nums, k):
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=freq.get)
# Bucket sort approach (optimal)
def top_k_frequent_bucket(nums, k):
freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
nums = [1, 1, 1, 2, 2, 3]
print(top_k_frequent(nums, 2)) # [1, 2]
8. Isomorphic Strings
Problem: Check if two strings are isomorphic.
def is_isomorphic(s, t):
s_to_t = {}
t_to_s = {}
for char_s, char_t in zip(s, t):
# Check s -> t mapping
if char_s in s_to_t:
if s_to_t[char_s] != char_t:
return False
else:
s_to_t[char_s] = char_t
# Check t -> s mapping
if char_t in t_to_s:
if t_to_s[char_t] != char_s:
return False
else:
t_to_s[char_t] = char_s
return True
print(is_isomorphic("egg", "add")) # True
print(is_isomorphic("foo", "bar")) # False
9. Minimum Window Substring
Problem: Find minimum window in s containing all characters of t.
from collections import Counter
def min_window(s, t):
if not s or not t:
return ""
required = Counter(t)
needed = len(required)
formed = 0
window = {}
left = 0
min_len = float('inf')
min_window = (0, 0)
for right, char in enumerate(s):
# Add char to window
window[char] = window.get(char, 0) + 1
# Check if this char's requirement is met
if char in required and window[char] == required[char]:
formed += 1
# Try to shrink window
while formed == needed and left <= right:
# Update result
if right - left + 1 < min_len:
min_len = right - left + 1
min_window = (left, right + 1)
# Remove leftmost char
char = s[left]
window[char] -= 1
if char in required and window[char] < required[char]:
formed -= 1
left += 1
return s[min_window[0]:min_window[1]] if min_len != float('inf') else ""
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
10. LRU Cache
Problem: Implement Least Recently Used cache.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
# Move to end (most recent)
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
# Update and move to end
self.cache.move_to_end(key)
self.cache[key] = value
# Remove oldest if over capacity
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# Usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # Evicts key 2
print(cache.get(2)) # -1 (not found)
Common Map Problem Patterns
- Index Mapping: Two sum, complement finding
- Frequency Counting: Most frequent, anagrams
- Sliding Window: Longest substring, minimum window
- Prefix Sums: Subarray sum problems
- State Mapping: Isomorphic strings, word pattern
- Caching: LRU cache, memoization