Dictionaries & sets

words = ["apple", "bob", "apple", "cy"]
lengths = {w: len(w) for w in words}
# {'apple': 5, 'bob': 3, 'cy': 2}
last = {w: i for i, w in enumerate(words)}
# {'apple': 2, 'bob': 1, 'cy': 3}: last index wins
pairs = dict(zip("abc", [1, 2, 3], strict=True))
# {'a': 1, 'b': 2, 'c': 3}
 
shared: dict[str, list[int]] = dict.fromkeys("ab", [])
shared["a"].append(1)
print(shared)  # {'a': [1], 'b': [1]}: one list
# the fix: a new list per key
own: dict[str, list[int]] = {k: [] for k in "ab"}

stock = {"apple": 3, "pear": 0}
stock["apple"]  # 3
stock.get("kiwi")  # None
stock.get("kiwi", 0)  # 0
"pear" in stock  # True: in checks the keys
0 in stock.values()  # True: a linear scan of the values
 
stock["kiwi"] = 5  # a new key goes last
stock["apple"] = 4  # an overwrite keeps its place
list(stock)  # ['apple', 'pear', 'kiwi']
stock.setdefault("fig", 1)  # 1: inserted
stock.setdefault("fig", 9)  # 1: already there
stock.pop("pear")  # 0
stock.pop("plum", None)  # None: no KeyError
stock.popitem()  # ('fig', 1): the last inserted
stock  # {'apple': 4, 'kiwi': 5}

from operator import itemgetter
 
score = {"ann": 90, "bo": 72, "cy": 90}
keys = score.keys()
score["di"] = 85
list(keys)  # ['ann', 'bo', 'cy', 'di']: a live view
 
score.keys() & {"bo", "zed"}  # {'bo'}
sorted(score.keys() - {"bo"})  # ['ann', 'cy', 'di']
max(score, key=score.__getitem__)  # 'ann': first of ties
sorted(score.items(), key=itemgetter(1), reverse=True)
# [('ann', 90), ('cy', 90), ('di', 85), ('bo', 72)]
sorted(score, key=lambda k: (-score[k], k))  # score, name
# ['ann', 'cy', 'di', 'bo']
 
for name in list(score):  # a snapshot: safe to delete
    if score[name] < 80:
        del score[name]
score  # {'ann': 90, 'cy': 90, 'di': 85}

from dataclasses import dataclass
 
d = {1: "int", 1.0: "float", True: "bool"}
print(d)  # {1: 'bool'}: 1 == 1.0 == True, so one key
 
grid = {(0, 1): "#"}  # tuple keys: coordinates
grid[0, 1]  # '#': the parentheses are optional
 
 
@dataclass(frozen=True)
class Point:
    x: int
    y: int
 
 
seen = {Point(1, 2)}
Point(1, 2) in seen  # True: hashed by field values
 
path = [1, 2]
by_path = {tuple(path): 1}  # a list key raises TypeError
hash(-1) == hash(-2)  # True in CPython; still two keys

import copy
from collections import OrderedDict
 
base = {"db": {"host": "x", "port": "1"}}
over = {"db": {"host": "y"}}
base | over  # {'db': {'host': 'y'}}: port is gone
# | replaces whole values; deep merge is in Recipes
 
shallow = base.copy()
shallow["db"]["host"] = "z"  # base changes too
deep = copy.deepcopy(base)  # shares nothing
 
{"a": 1, "b": 2} == {"b": 2, "a": 1}  # True
od1 = OrderedDict(a=1, b=2)
od2 = OrderedDict(b=2, a=1)
od1 == od2, od1 == dict(od2)  # (False, True)

from collections import Counter, OrderedDict, defaultdict
 
c = Counter("abracadabra")
c["a"], c["z"]  # (5, 0)
"z" in c  # False: reading a missing key didn't insert it
c.most_common(2)  # [('a', 5), ('b', 2)]
c.total()  # 11
Counter(a=3, b=1) - Counter(a=1, b=2)  # Counter({'a': 2})
Counter("aab") <= Counter("aabbc")  # True: fits inside
 
graph: defaultdict[str, list[str]] = defaultdict(list)
graph["a"].append("b")
graph["c"]  # [], and "c" is now a key
sorted(graph)  # ['a', 'c']
 
lru: OrderedDict[str, int] = OrderedDict(a=1, b=2, c=3)
lru.move_to_end("a")  # a is now the newest
lru.popitem(last=False)  # ('b', 2): evict the oldest

a = {1, 2, 3}
b = {3, 4}
a | b, a & b, a - b, a ^ b
# ({1, 2, 3, 4}, {3}, {1, 2}, {1, 2, 4})
{1, 2} <= a, a < a, a.isdisjoint({9})  # (True, False, True)
a.union([5, 6])  # methods take any iterable
# a | [5, 6] raises TypeError
 
seen: set[tuple[int, int]] = set()
seen.add((0, 0))  # coordinates as tuples
(0, 0) in seen  # True
 
state = frozenset({"key", "door"})
best = {state: 3}  # an unordered state as a key
best[frozenset({"door", "key"})]  # 3
 
lists = [[1, 2, 3, 4], [2, 3, 5], [3, 2, 9]]
set.intersection(*map(set, lists))  # {2, 3}: in every list
sorted(set().union(*lists))  # [1, 2, 3, 4, 5, 9]
sorted(set("hello"))  # ['e', 'h', 'l', 'o']: sort to show

FRUITS = ["apple", "banana", "cherry", "date"]
bit = {f: 1 << i for i, f in enumerate(FRUITS)}
 
a = bit["apple"] | bit["cherry"]
b = bit["cherry"] | bit["date"]
both, either = a & b, a | b
only_a = a & ~b
bin(either), either.bit_count()  # ('0b1101', 3)
a & either == a  # True: a is a subset of either
 
 
def members(mask: int) -> list[str]:
    out: list[str] = []
    while mask:
        low = mask & -mask  # the lowest set bit
        out.append(FRUITS[low.bit_length() - 1])
        mask ^= low
    return out
 
 
members(only_a), members(both)  # (['apple'], ['cherry'])

import sys
 
sys.getsizeof({})  # 64: an empty dict (64-bit CPython)
sys.getsizeof({i: i for i in range(1000)})  # 36952
sys.getsizeof(set())  # 216
 
R, C = 3, 4
by_tuple = {(r, c): 0 for r in range(R) for c in range(C)}
by_int = {r * C + c: 0 for r in range(R) for c in range(C)}
r, c = divmod(7, C)  # back from an int key: (1, 3)

from collections import defaultdict
 
 
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i  # after the check: no self-pairs
    return []
 
 
def count_sums(nums: list[int], k: int) -> int:
    count = {0: 1}  # the empty prefix
    pre = ans = 0
    for x in nums:
        pre += x
        ans += count.get(pre - k, 0)
        count[pre] = count.get(pre, 0) + 1
    return ans
 
 
print(two_sum([3, 2, 4], 6))  # [1, 2]
print(count_sums([1, 1, 1], 2))  # 2
 
edges = [("a", "b"), ("b", "c")]
g: defaultdict[str, list[str]] = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
print(dict(g))  # {'a': ['b'], 'b': ['a', 'c'], 'c': ['b']}

from collections import Counter, defaultdict
from collections.abc import Mapping
from typing import NotRequired, TypedDict
 
 
def total(prices: Mapping[str, float]) -> float:
    return sum(prices.values())
 
 
counts: dict[str, int] = {"a": 1}
total(counts)  # OK: Mapping is covariant in its values
floats: dict[str, float] = counts  # ❌ type error: invariant
empty: dict[str, list[int]] = {}  # annotate empty dicts
groups: defaultdict[str, list[int]] = defaultdict(list)
freq: Counter[str] = Counter("abca")
 
 
class User(TypedDict):
    id: int
    name: str
    email: NotRequired[str]
 
 
u: User = {"id": 1, "name": "ann"}  # email may be absent
type Trie = dict[str, Trie]  # a recursive alias (3.12+)

from collections import defaultdict
 
owner = {"ann": "red", "bo": "blue", "cy": "red"}
by_color: defaultdict[str, list[str]] = defaultdict(list)
for name, color in owner.items():
    by_color[color].append(name)
print(dict(by_color))
# {'red': ['ann', 'cy'], 'blue': ['bo']}
 
unique = {"a": 1, "b": 2}
print({v: k for k, v in unique.items()})  # {1: 'a', 2: 'b'}

from typing import Any
 
 
def deep_merge(
    a: dict[str, Any], b: dict[str, Any]
) -> dict[str, Any]:
    out = dict(a)
    for k, v in b.items():
        old = out.get(k)
        if isinstance(old, dict) and isinstance(v, dict):
            out[k] = deep_merge(old, v)
        else:
            out[k] = v
    return out
 
 
base = {"db": {"host": "x", "port": 5432}, "debug": False}
env = {"db": {"host": "prod"}, "debug": True}
print(deep_merge(base, env))
# {'db': {'host': 'prod', 'port': 5432}, 'debug': True}

type Trie = dict[str, Trie]
END = "$"  # not a letter, so it can't clash
 
 
def insert(root: Trie, word: str) -> None:
    node = root
    for ch in word:
        node = node.setdefault(ch, {})
    node[END] = {}
 
 
def walk(root: Trie, s: str) -> Trie | None:
    node = root
    for ch in s:
        if ch not in node:
            return None
        node = node[ch]
    return node
 
 
root: Trie = {}
for w in ["car", "cart", "cat"]:
    insert(root, w)
found = walk(root, "car")
print(found is not None and END in found)  # True: a word
print(walk(root, "ca") is not None)  # True: a prefix
print(walk(root, "cow"))  # None

def longest_run(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue  # not the start of a run
        y = x
        while y + 1 in s:
            y += 1
        best = max(best, y - x + 1)
    return best
 
 
print(longest_run([100, 4, 200, 1, 3, 2]))  # 4: 1 to 4

from collections import deque
from string import ascii_lowercase
 
 
def ladder(begin: str, end: str, words: list[str]) -> int:
    unseen = set(words)  # remove a word once it's queued
    if end not in unseen:
        return 0
    unseen.discard(begin)
    q = deque([(begin, 1)])
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in ascii_lowercase:
                nxt = word[:i] + ch + word[i + 1 :]
                if nxt in unseen:
                    unseen.remove(nxt)  # mark on enqueue
                    q.append((nxt, steps + 1))
    return 0
 
 
words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladder("hit", "cog", words))  # 5
print(ladder("hit", "cog", words[:-1]))  # 0

def is_happy(n: int) -> bool:
    seen: set[int] = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1
 
 
print(is_happy(19), is_happy(2))  # True False

from collections import Counter
 
 
def can_build(note: str, letters: str) -> bool:
    return Counter(note) <= Counter(letters)  # 3.10+
 
 
print(can_build("aab", "baa"), can_build("aa", "ab"))
# True False
missing = Counter("aabc") - Counter("ab")
print(sorted(missing.elements()))  # ['a', 'c']

import heapq
from collections import Counter
 
words = "the cat and the hat and the bat".split()
cnt = Counter(words)
ranked = sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0]))
print(ranked[:3])  # [('the', 3), ('and', 2), ('bat', 1)]
top = heapq.nsmallest(
    2, cnt.items(), key=lambda kv: (-kv[1], kv[0])
)  # [('the', 3), ('and', 2)]

def longest_k_distinct(s: str, k: int) -> int:
    count: dict[str, int] = {}
    lo = best = 0
    for hi, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:
            gone = s[lo]
            count[gone] -= 1
            if count[gone] == 0:
                del count[gone]  # else len(count) lies
            lo += 1
        best = max(best, hi - lo + 1)
    return best
 
 
print(longest_k_distinct("eceba", 2))  # 3: "ece"