4. Tuples, Sets & Dicts

Tutorial

Tuple: Immutable sequence — hashable, usable as dict key or set element. Great for coordinates, state keys in DP.

Set: Unordered unique collection — $O(1)$ average membership test.

Dict: Hash map — $O(1)$ average insert/lookup/delete.

# ══ TUPLES ══════════════════════════════════════════════════════
point = (3, 7)
single = (5,)                  # single-element tuple needs trailing comma
empty_t = ()
x, y  = point                  # unpack
a, *rest = (1, 2, 3, 4)        # extended unpack: a=1, rest=[2,3,4]

# Tuples as hashable keys
visited = set()
visited.add((row, col))        # grid cell as state key
dp = {}
dp[(i, j, state)] = value      # 3D DP key

# Comparison is lexicographic — useful in heaps
(1, 5) < (1, 7)   # True
(0, 9) < (1, 0)   # True

# ══ SETS ════════════════════════════════════════════════════════
s = {1, 2, 3}
s = set([1, 2, 2, 3])   # {1, 2, 3}
empty = set()            # NOT {} — that's an empty dict!

s.add(4)                 # O(1)
s.remove(2)              # O(1) — KeyError if missing
s.discard(2)             # O(1) — safe
5 in s                   # O(1) ← key advantage over list

a = {1,2,3,4}; b = {3,4,5,6}
a | b   # union:        {1,2,3,4,5,6}
a & b   # intersection: {3,4}
a - b   # difference:   {1,2}
a ^ b   # symmetric:    {1,2,5,6}
a <= b  # is subset?

# Common DSA pattern: deduplicate (order not preserved)
unique = list(set([1, 2, 2, 3, 3]))   # [1, 2, 3]

# ══ DICTS ═══════════════════════════════════════════════════════
d = {"a": 1, "b": 2}
d = dict(a=1, b=2)  # same, alternate constructor
d["a"]             # 1 — KeyError if missing
d.get("z", 0)      # 0 — safe default

d["c"] = 3         # O(1) insert/update
del d["a"]         # O(1) — KeyError if missing
d.pop("b")         # O(1) — returns value
d.pop("z", None)   # safe delete

"a" in d           # O(1) key check
"a" in d.keys()    # same but slower (creates a view)

for k in d:               # iterate keys
    print(k, d[k])
for k, v in d.items():   # iterate key-value pairs — most common
    print(k, v)
for v in d.values():     # iterate values only
    print(v)
list(d.keys())    # ['a', 'b']
list(d.values())  # [1, 2]
list(d.items())   # [('a',1), ('b',2)]

# Python 3.9+: dict merge operator
merged = d1 | d2      # new merged dict (d2 wins on conflict)
d1 |= d2              # update d1 in-place

# defaultdict — auto-init missing keys
from collections import defaultdict
graph  = defaultdict(list)
freq   = defaultdict(int)
nested = defaultdict(lambda: defaultdict(int))

# Counter — frequency map
from collections import Counter
c = Counter("abracadabra")
c.most_common(3)     # [('a',5),('b',2),('r',2)]
c["z"]               # 0 — no KeyError
c.total()            # 11 — Python 3.10+: total count
c1 + c2; c1 - c2; c1 & c2; c1 | c2  # arithmetic

Reference

Container	Lookup	Insert	Delete	Notes
list	$O(n)$	$O(1)$† end	$O(n)$	Use set for membership
set	$O(1)$	$O(1)$†	$O(1)$	Unordered, unique
dict	$O(1)$	$O(1)$†	$O(1)$	Key→value mapping
tuple	$O(1)$ index	immutable	immutable	Hashable
defaultdict	$O(1)$	$O(1)$†	$O(1)$	Auto-init missing keys
Counter	$O(1)$	$O(1)$†	$O(1)$	c["miss"]=0, .total() 3.10+
dict | merge	—	—	—	3.9+: d1 | d2

† Amortized

---