Hash Tables

Hash Tables

# Average O(1) insert/lookup/delete
# Worst case O(n) all keys hash to same bucket

# Python dict
d = {}
d['key'] = 'value'     # O(1) average
val = d.get('key')     # O(1), None if absent
'key' in d             # O(1)
del d['key']           # O(1)

# Frequency counter (very common pattern)
from collections import Counter
count = Counter([1,2,2,3,3,3])
print(count.most_common(2))  # [(3,3),(2,2)]

# Two Sum -- O(n) with hash map
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 []

# Anagram check
def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Group anagrams
from collections import defaultdict
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups[tuple(sorted(s))].append(s)
    return list(groups.values())