13. DSA Standard Library

collections

from collections import deque, defaultdict, Counter, OrderedDict

# ── deque ────────────────────────────────────────────────────────
dq = deque([1, 2, 3])
dq.append(4)         # O(1) — right
dq.appendleft(0)     # O(1) — left
dq.pop()             # O(1) — right
dq.popleft()         # O(1) — left (list.pop(0) is O(n)!)
dq[0]; dq[-1]        # peek left/right
dq.rotate(1)         # rotate right: [0,1,2,3] → [3,0,1,2]
deque(maxlen=k)      # fixed-size: auto-drops oldest on append

# ── defaultdict ──────────────────────────────────────────────────
graph = defaultdict(list)
graph[u].append(v)   # no KeyError on first access

# ── Counter ──────────────────────────────────────────────────────
c = Counter([1,2,2,3,3,3])
c.most_common(2)       # [(3,3),(2,2)]
c.total()              # 6  — 3.10+
c.elements()           # iterator: 1,2,2,3,3,3
del c[1]               # remove key
c.subtract([3,3])      # in-place subtraction (can go negative)

# ── OrderedDict ──────────────────────────────────────────────────
od = OrderedDict()
od["a"] = 1; od["b"] = 2
od.move_to_end("a")         # move "a" to end (mark as recently used)
od.move_to_end("b", last=False)  # move to front (mark as oldest)
od.popitem(last=False)      # remove and return first inserted
# Used for LRU Cache implementation

heapq

import heapq

# Min-heap
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappop(h)            # 2
h[0]                        # peek minimum — O(1)
heapq.heapify(lst)          # build heap in O(n)
heapq.heapreplace(h, x)     # pop min + push x in one O(log n) op
heapq.nlargest(k, it)       # k largest; uses heap of size k
heapq.nsmallest(k, it)      # k smallest

# Max-heap: negate values
heapq.heappush(h, -val)
max_val = -heapq.heappop(h)

# Heap of (priority, value) tuples
heapq.heappush(h, (dist, node))   # compare by dist first, then node
pri, val = heapq.heappop(h)

# Tie-break without comparing values (when values aren't comparable)
import itertools
_counter = itertools.count()
heapq.heappush(h, (priority, next(_counter), value))

bisect

import bisect

arr = [1, 3, 5, 7, 9]

# Core functions
bisect.bisect_left(arr, 5)    # 2 — index of first element ≥ 5
bisect.bisect_right(arr, 5)   # 3 — index of first element > 5

# Python 3.10+: key parameter (like sort key)
data = [(1,"a"),(3,"b"),(5,"c")]
bisect.bisect_left(data, 3, key=lambda x: x[0])   # 1

# Derived operations
def contains(arr, x):
    i = bisect.bisect_left(arr, x)
    return i < len(arr) and arr[i] == x

def count_in_sorted(arr, x) -> int:
    return bisect.bisect_right(arr, x) - bisect.bisect_left(arr, x)

def floor_val(arr, x):    # largest element ≤ x
    i = bisect.bisect_right(arr, x) - 1
    return arr[i] if i >= 0 else None

def ceil_val(arr, x):     # smallest element ≥ x
    i = bisect.bisect_left(arr, x)
    return arr[i] if i < len(arr) else None

# Insert maintaining sort — O(n) due to shift (for small k, ok)
bisect.insort_left(arr, 4)    # [1,3,4,5,7,9]

math

import math

math.sqrt(25)            # 5.0
math.isqrt(25)           # 5    — integer sqrt, exact
math.floor(3.7)          # 3
math.ceil(3.2)           # 4
math.gcd(12, 8)          # 4
math.gcd(12, 8, 6)       # 2    — 3.9+: multi-arg gcd
math.lcm(4, 6)           # 12   — 3.9+
math.lcm(4, 6, 9)        # 36   — 3.9+: multi-arg lcm
math.log2(8)             # 3.0
math.log(100, 10)        # 2.0
math.comb(10, 3)         # 120  — C(n,k) = n! / (k!(n-k)!)
math.perm(5, 2)          # 20   — P(n,k) = n! / (n-k)!
math.factorial(10)       # 3628800
math.cbrt(27.0)          # 3.0  — 3.11+: cube root
math.exp2(10)            # 1024.0 — 3.11+: 2^x
math.inf                 # positive infinity
math.pi; math.e          # constants

functools & itertools

from functools import cache, lru_cache, cmp_to_key, reduce
from itertools import (accumulate, combinations, permutations,
                       product, chain, zip_longest, count, islice)

# accumulate — running totals
list(accumulate([1,2,3,4,5]))           # [1,3,6,10,15]
list(accumulate([1,2,3,4], max))        # [1,2,3,4] — running max
prefix = [0] + list(accumulate(arr))    # 0-indexed prefix sums

# combinations / permutations
list(combinations([1,2,3], 2))          # [(1,2),(1,3),(2,3)]
list(permutations([1,2,3], 2))          # all ordered pairs
list(product([0,1], repeat=3))          # all 3-bit strings
list(product("ABCD", repeat=2))         # cartesian product

# chain — flatten one level
list(chain([1,2],[3,4],[5]))            # [1,2,3,4,5]
list(chain.from_iterable([[1,2],[3,4]])) # same

# zip_longest
list(zip_longest([1,2,3],[4,5], fillvalue=0))  # [(1,4),(2,5),(3,0)]

# reduce
from functools import reduce
reduce(lambda a,b: a*b, [1,2,3,4,5])   # 120

# count — infinite counter (useful for tie-breaking in heaps)
c = count()
next(c); next(c)    # 0, 1, 2, ...

---