Hash Tables

A hash table maps keys to values using a hash function. Python's dict and set are hash tables with O(1) average insert, lookup and delete.

Counting

counting.py

from collections import Counter

words = ["a", "b", "a", "c", "a"]
print(Counter(words).most_common(1))  # [('a', 3)]

Two Sum

two_sum.py

def two_sum(nums, target):
    index = {}                       # value -> position
    for i, x in enumerate(nums):
        need = target - x
        if need in index:
            return [index[need], i]
        index[x] = i
    return []                        # O(n) time, O(n) space

Grouping anagrams

anagrams.py

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())