The previous two chapters were about ideas: what a hash table is, why a heap gives you the smallest element in logarithmic time, when divide-and-conquer beats brute force. This chapter is about how those ideas turn into running code. The language we use is Python — not because it is the fastest, but because it gets out of the way. Its standard library is, in effect, the catalog from Chapter 21 already built, tested, and tuned in C. Knowing which batteries are included — and the handful of idioms that quietly change a program's complexity class — is what separates code that merely works from code that works at scale.
Why Python for this. Python is the closest thing the field has to executable pseudocode. A binary search reads almost exactly like its description; a graph is a dictionary of lists. That transparency is the point: the structure of the solution should be visible through the syntax, not buried under boilerplate. Everything here applies conceptually to any language — only the spelling changes.
The Built-in Containers, and What They Really Are
Python's four workhorse containers are direct embodiments of structures from Chapter 21. Recognizing the structure underneath the convenient syntax is what lets you predict performance.
| Container |
Underlying structure |
Lookup |
Notes |
list |
Dynamic array |
O(n) by value, O(1) by index |
Amortized O(1) append/pop; O(n) insert(0,..)/pop(0) |
dict |
Hash table |
O(1) average |
Insertion-ordered since Python 3.7 |
set |
Hash table (keys only) |
O(1) average |
Membership, dedup, set algebra |
tuple |
Immutable array |
O(1) by index |
Hashable → usable as a dict key or set member |
The single most consequential thing to internalize is the difference between the two O(1)-vs-O(n) membership tests:
# 'x in a_list' scans every element — O(n)
if user_id in banned_list: # slow when the list is large
...
# 'x in a_set' hashes once and probes — O(1) average
if user_id in banned_set: # the version that survives scale
...
A loop that checks membership against a list is a quadratic algorithm wearing a linear disguise — one of the most common causes of code that is fast in testing and catastrophic in production. Converting the lookup target to a set once, up front, collapses the inner cost to constant time.
Analogy: A list is a numbered row of lockers — to find whether a particular item is inside, you open every locker. A set is the index card system at a library: one hash of the title tells you exactly which drawer to check. Same items, completely different cost to ask "is this here?"
Two container traps deserve naming because they bite nearly everyone once:
# Building a 2D grid. The right way:
grid = [[0] * cols for _ in range(rows)] # each row is its own list
# The wrong way — every row is the SAME list object:
grid = [[0] * cols] * rows # writing grid[0][0] changes all rows
# A mutable default argument is created ONCE, at definition time, and shared:
def add(item, bucket=[]): # bug: bucket persists across calls
bucket.append(item); return bucket
def add(item, bucket=None): # the safe idiom
if bucket is None: bucket = []
bucket.append(item); return bucket
The Standard Library Is the Data-Structure Catalog
Most of Chapter 21 ships in the box. Reaching for these instead of hand-rolling is not laziness — the library versions are correct, C-optimized, and instantly recognizable to any reader.
collections — the everyday upgrades. A Counter is a multiset and a frequency map in one; defaultdict removes the "check-then-initialize" dance; a deque is the real queue.
from collections import Counter, defaultdict, deque
Counter("mississippi").most_common(1) # [('i', 4)] — frequency in one line
graph = defaultdict(list) # no KeyError on first touch
graph[u].append(v) # the node auto-creates an empty list
queue = deque([start]) # popleft() is O(1); list.pop(0) is O(n)
queue.append(x); queue.popleft()
The deque distinction is not academic. A breadth-first search built on a plain list with pop(0) is O(n²) because every dequeue shifts the entire list left; the same code on a deque is O(n). The queue from Chapter 21 only behaves like a queue when its backing structure supports O(1) removal from the front.
heapq — the priority queue. Python's heap is a min-heap living inside an ordinary list. It is the engine behind Dijkstra's algorithm and every "top-K" problem.
import heapq
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap) # O(n)
heapq.heappush(heap, 2) # O(log n)
heapq.heappop(heap) # O(log n) → 1, the minimum
heap[0] # O(1) peek at the minimum — don't pop to look
# Need a max-heap? Negate on the way in and out:
max_heap = [-x for x in data]; heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap)
# Keyed priority: push tuples; ties break on a counter so payloads never compare
heapq.heappush(pq, (priority, next(counter), payload))
Analogy: A heap is a hospital triage desk. It does not keep a fully sorted list of every patient — that would be wasted effort. It guarantees exactly one thing cheaply: the most urgent case is always at the front. Inserting a new patient or removing the current most-urgent one is quick; asking for a full ranking is not what it is for.
bisect — binary search you don't have to re-derive. Maintaining a sorted list and querying it is so common that the binary search of Chapter 22 is packaged directly.
import bisect
a = [1, 3, 4, 7, 10]
bisect.bisect_left(a, 4) # 2 — first index where a[i] >= 4
bisect.insort(a, 5) # insert 5, keeping the list sorted
# Count values in [lo, hi]: bisect_right(a, hi) - bisect_left(a, lo)
Idioms That Quietly Change the Complexity
A few Python habits are not stylistic preferences — they decide whether a routine is linear or quadratic.
# Building a string. '+=' in a loop is O(n²): each step copies the whole string.
out = "".join(pieces) # O(n) — the only correct way to assemble strings
# Comprehensions over manual append loops: clearer and faster
squares = [x * x for x in nums]
# Generators are lazy — they compute one value at a time, holding nothing in memory
total = sum(x * x for x in range(10**8)) # no 100-million-element list is built
The generator point matters beyond memory: laziness lets any() and all() short-circuit, stopping at the first decisive element instead of scanning the whole sequence. The cost of a stream-processing pipeline can hinge entirely on whether its stages are lazy.
Turning the Paradigms into Templates
The four paradigms from Chapter 22 are powerful precisely because each collapses into a near-mechanical skeleton. Once you recognize the shape of a problem, the code almost writes itself — the thinking is in the recognition, not the typing.
Two pointers / sliding window turn many O(n²) scans into a single linear pass by maintaining a window instead of re-examining every pair:
def longest_unique(s): # longest substring with no repeats — O(n)
seen, left, best = {}, 0, 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1 # jump the window past the duplicate
seen[ch] = right
best = max(best, right - left + 1)
return best
Graph traversal (Chapter 22's BFS/DFS) is the same template every time — only the data structure holding the frontier changes. A queue gives breadth-first (and shortest paths on unweighted graphs); a stack or the call stack gives depth-first:
def bfs(graph, start):
seen, queue = {start}, deque([start])
while queue:
node = queue.popleft() # swap for stack.pop() to get DFS
for nb in graph[node]:
if nb not in seen:
seen.add(nb); queue.append(nb)
Dynamic programming top-down is, in Python, often a one-line decorator away — lru_cache is memoization. The transformation from exponential to linear that Chapter 22 described mechanically becomes:
from functools import lru_cache
@lru_cache(maxsize=None) # adds the cache; the logic is unchanged
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
Backtracking is depth-first search over partial solutions, and its skeleton is always choose → recurse → undo:
def subsets(nums):
out = []
def backtrack(start, path):
out.append(path[:]) # record the current partial solution
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1, path) # recurse
path.pop() # undo — restore state for the next branch
backtrack(0, [])
return out
Binary search on the answer generalizes Chapter 22's search: when a problem asks for the smallest (or largest) value satisfying a monotonic condition, binary-search the answer space rather than an array. "What is the slowest eating speed that still finishes in time?" and "what is the smallest ship capacity that delivers in N days?" are the same problem — find the threshold where a yes/no test flips.
Diagnosing a Problem: From Signal to Tool
Most of the difficulty in applying this toolkit is recognition — matching the texture of a problem to the structure that solves it. These pairings come up again and again:
| When you see… |
Reach for… |
| "Top K", "K largest / smallest / closest" |
Heap (heapq) |
| "Subarray / substring sum equals K" |
Prefix sums + hash map |
| "Longest / shortest window satisfying…" |
Sliding window |
| "All permutations / subsets / combinations" |
Backtracking |
| "Overlapping subproblems", "in how many ways" |
Dynamic programming |
| "Next greater / smaller element" |
Monotonic stack |
| "Connected regions", "islands", "groups" |
BFS/DFS or Union-Find |
| "Shortest path", unweighted vs. weighted |
BFS vs. Dijkstra |
| "Ordering with prerequisites" |
Topological sort |
| "Prefix / autocomplete" |
Trie |
| Sorted input + a target |
Binary search or two pointers |
The input size is itself a hint about the target complexity — the upper bound on n quietly tells you which paradigms are even admissible:
| Input size |
Feasible complexity |
Typical approach |
| n ≤ 12 |
O(n!) |
brute-force permutations, backtracking |
| n ≤ 25 |
O(2ⁿ) |
subset enumeration, bitmask DP |
| n ≤ 500 |
O(n³) |
interval DP, Floyd–Warshall |
| n ≤ 5,000 |
O(n²) |
nested loops, 2D DP |
| n ≤ 10⁶ |
O(n log n) |
sorting, heaps, BFS/DFS |
| n ≤ 10⁸ |
O(n) |
single pass, prefix sums, hashing |
| n > 10⁸ |
O(log n) or O(1) |
binary search, closed-form math |
The senior takeaway: the leap from competent to expert here is not memorizing more algorithms — it is faster diagnosis. Reading "find the K most frequent" and immediately seeing a Counter feeding a heap, or "smallest value that works" and reaching for binary search on the answer, is the skill. The library and the templates above are the vocabulary; recognizing which sentence to write is the fluency.
The Complete Reference
The narrative above explains why each tool exists and when to reach for it. What follows is the lab manual: a complete, runnable Python reference covering every structure, algorithm, and idiom in this chapter, organized for scanning. Nothing here is decorative — each block is code you can paste and run.
"""
╔══════════════════════════════════════════════════════════════════════════════╗
║ PYTHON REFERENCE — COMPLETE REFERENCE GUIDE ║
║ Data structures, algorithms, and the idioms that tie them ║
╚══════════════════════════════════════════════════════════════════════════════╝
TABLE OF CONTENTS
─────────────────
1. Python Fundamentals & Syntax
2. Data Types & Type System
3. Strings & String Methods
4. Lists, Tuples, Sets, Dicts — Deep Dive
5. Comprehensions & Generators
6. Functions — Args, Kwargs, Closures, Decorators
7. Object-Oriented Programming (OOP)
8. Iterators & Itertools
9. Error Handling & Context Managers
10. File I/O
11. Sorting, Searching, Custom Comparators
12. Bit Manipulation
13. Collections Module
14. Heapq & Priority Queues
15. Functional Programming (map, filter, reduce, lambda)
16. Recursion & Memoization
17. Dynamic Programming Patterns
18. Graph Algorithms
19. Tree Algorithms
20. Linked List Patterns
21. Sliding Window & Two Pointers
22. Binary Search Patterns
23. Stack & Queue Patterns
24. Backtracking
25. Greedy Algorithms
26. Complexity Cheat Sheet
27. Python-Specific Tricks
28. Common Patterns Summary
"""
1. Python Fundamentals & Syntax
# --- Variable assignment & multiple assignment ---
x = 10
a, b, c = 1, 2, 3
a, b = b, a # Swap without temp variable
# --- Unpacking ---
first, *rest = [1, 2, 3, 4, 5] # first=1, rest=[2,3,4,5]
*init, last = [1, 2, 3, 4, 5] # init=[1,2,3,4], last=5
first, *mid, last = [1, 2, 3, 4] # first=1, mid=[2,3], last=4
# --- Truthiness / Falsiness ---
# Falsy: False, None, 0, 0.0, "", [], {}, set(), ()
# Truthy: everything else
# --- Walrus operator := (Python 3.8+) — assign & evaluate in one expression ---
import re
if m := re.search(r'\d+', "abc123"):
print(m.group()) # "123"
# Useful in while loops:
# while chunk := file.read(8192):
# process(chunk)
# --- Ternary expression ---
val = "even" if x % 2 == 0 else "odd"
# --- Chained comparisons ---
result = 1 < x < 100 # Pythonic, evaluates correctly
# --- None checks — always use `is` not `==` ---
if x is None:
pass
if x is not None:
pass
# --- f-strings (Python 3.6+) ---
name = "Ada"
print(f"Hello {name}, x={x:.2f}") # Format floats
print(f"{x!r}") # repr
print(f"{1_000_000:,}") # 1,000,000
print(f"{'left':<10}|{'right':>10}")# Alignment
# --- Pass, continue, break, else on loops ---
for i in range(10):
if i == 3: continue
if i == 7: break
else:
print("Loop completed without break") # Only runs if no break hit
# --- Global & nonlocal ---
counter = 0
def increment():
global counter
counter += 1
def make_counter():
count = 0
def inc():
nonlocal count
count += 1
return count
return inc
2. Data Types & Type System
# --- Numeric types ---
i = 42 # int (arbitrary precision)
f = 3.14 # float (64-bit double)
c = 3 + 4j # complex
from fractions import Fraction
frac = Fraction(1, 3) # Exact rational arithmetic
# --- Integer tricks ---
print(10 // 3) # 3 — floor division
print(-10 // 3) # -4 — floor (rounds toward -inf, NOT toward zero!)
print(10 % 3) # 1
print(-10 % 3) # 2 — Python modulo always non-negative when divisor positive
print(divmod(10, 3)) # (3, 1) — quotient and remainder together
print(2 ** 10) # 1024
print(abs(-5)) # 5
print(pow(2, 10, 1000)) # 24 — modular exponentiation, O(log n)
# --- Float gotchas ---
print(0.1 + 0.2 == 0.3) # False!
import math
print(math.isclose(0.1 + 0.2, 0.3)) # True
# --- Type conversion ---
int("42"), int(3.9) # 42, 3 (truncates, does NOT round)
float("3.14")
str(42)
bool(0), bool(""), bool([]) # False, False, False
list("abc") # ['a', 'b', 'c']
tuple([1, 2, 3])
set([1, 1, 2, 3]) # {1, 2, 3}
# --- Type checking ---
isinstance(42, int) # True
isinstance(42, (int, float)) # True — checks multiple types
type(42) is int # True — exact type, no inheritance
# --- Constants ---
import sys
print(sys.maxsize) # 9223372036854775807 (2^63 - 1 on 64-bit)
print(float('inf')) # Infinity
print(float('-inf')) # -Infinity
print(float('nan')) # NaN
INF = float('inf')
3. Strings & String Methods
s = "Hello, World!"
# --- Basics ---
len(s) # 13
s[0], s[-1] # 'H', '!'
s[7:12] # 'World'
s[::-1] # Reverse: '!dlroW ,olleH'
s.lower(), s.upper()
s.strip(), s.lstrip(), s.rstrip()
s.replace("World", "Python")
s.split(",") # ['Hello', ' World!']
",".join(["a", "b", "c"]) # 'a,b,c'
# --- Search ---
s.find("World") # 7, returns -1 if not found
s.index("World") # 7, raises ValueError if not found
s.count("l") # 3
s.startswith("Hello") # True
s.endswith("!") # True
"World" in s # True
# --- Check content ---
"abc".isalpha() # True
"123".isdigit() # True
"abc123".isalnum() # True
" ".isspace() # True
# --- Formatting ---
"Hello {}".format("World")
"{0} {1} {0}".format("ha", "ha!")
"{name}".format(name="Ada")
# --- Useful patterns ---
# Count character frequencies
from collections import Counter
Counter("mississippi") # Counter({'s': 4, 'i': 4, 'p': 2, 'm': 1})
# Anagram check
def is_anagram(s, t):
return Counter(s) == Counter(t)
# Palindrome check
def is_palindrome(s):
s = s.lower()
return s == s[::-1]
# --- String to list of chars and back ---
chars = list("hello") # ['h', 'e', 'l', 'l', 'o']
"".join(chars) # 'hello'
# --- ord and chr ---
ord('a') # 97
chr(97) # 'a'
ord('A') # 65
# Lowercase letter index: ord(c) - ord('a') → 0..25
# Check if lowercase: 'a' <= c <= 'z'
# --- String multiplication ---
"ab" * 3 # 'ababab'
"-" * 20 # '--------------------'
# --- Partition ---
"hello=world".partition("=") # ('hello', '=', 'world')
# --- Encoding ---
"hello".encode("utf-8") # b'hello'
b"hello".decode("utf-8") # 'hello'
4. Lists, Tuples, Sets, Dicts — Deep Dive
# ===== LISTS =====
# Ordered, mutable, allows duplicates. O(1) append/pop, O(n) insert/delete.
lst = [3, 1, 4, 1, 5, 9, 2, 6]
lst.append(7) # Add to end: O(1)
lst.pop() # Remove & return last: O(1)
lst.pop(0) # Remove & return index 0: O(n)
lst.insert(0, 99) # Insert at index: O(n)
lst.remove(1) # Remove first occurrence of value: O(n)
lst.index(5) # Find index of value: O(n)
lst.count(1) # Count occurrences: O(n)
lst.reverse() # In-place reverse: O(n)
lst.sort() # In-place sort: O(n log n)
lst.extend([10, 11]) # Append all from iterable: O(k)
lst.copy() # Shallow copy
lst.clear() # Remove all elements
# Slicing: lst[start:stop:step] — always returns a NEW list
lst = [0, 1, 2, 3, 4, 5]
lst[1:4] # [1, 2, 3]
lst[::2] # [0, 2, 4]
lst[::-1] # [5, 4, 3, 2, 1, 0]
lst[1:4] = [10, 20] # Replace slice in-place
# --- 2D list initialization (CORRECT way) ---
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)] # Each row is independent
# grid = [[0] * cols] * rows # WRONG! All rows share same reference
# --- Flatten a nested list ---
nested = [[1, 2], [3, 4], [5]]
flat = [x for sub in nested for x in sub] # [1, 2, 3, 4, 5]
import itertools
flat2 = list(itertools.chain.from_iterable(nested))
# ===== TUPLES =====
# Ordered, IMMUTABLE, allows duplicates. Hashable (can be dict key / set member).
t = (1, 2, 3)
t = 1, 2, 3 # Parentheses optional
single = (1,) # Single-element tuple — comma required!
x, y, z = t # Unpacking
# Named tuples — lightweight struct
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
p.x, p.y # Access by name
p[0], p[1] # Still indexable
# ===== SETS =====
# Unordered, mutable, NO duplicates. O(1) average add/remove/lookup.
s = {1, 2, 3, 4}
s.add(5)
s.remove(5) # Raises KeyError if not found
s.discard(99) # No error if not found
s.pop() # Remove & return arbitrary element
# Set operations
a, b = {1, 2, 3}, {2, 3, 4}
a | b # Union: {1, 2, 3, 4}
a & b # Intersection: {2, 3}
a - b # Difference: {1}
a ^ b # Symmetric difference: {1, 4}
a.issubset(b)
a.issuperset(b)
a.isdisjoint(b)
# frozenset — immutable set, hashable
fs = frozenset([1, 2, 3])
# ===== DICTS =====
# Key-value pairs, ordered by insertion (Python 3.7+). O(1) average get/set/delete.
d = {"a": 1, "b": 2, "c": 3}
d["a"] # 1, raises KeyError if missing
d.get("z") # None (default)
d.get("z", 0) # 0 (custom default)
d["d"] = 4 # Insert/update
del d["a"] # Remove key
d.pop("b") # Remove & return value
d.pop("z", None) # Safe pop
d.keys() # dict_keys view
d.values() # dict_values view
d.items() # dict_items view (key, value) pairs
"a" in d # True — O(1) key lookup
d.update({"e": 5}) # Merge another dict in
{**d, "f": 6} # Merge with unpacking (Python 3.5+)
d | {"f": 6} # Merge operator (Python 3.9+)
# setdefault — get value, set it if missing
d.setdefault("new_key", []).append(1)
# defaultdict
from collections import defaultdict
dd = defaultdict(list)
dd["fruits"].append("apple") # No KeyError — auto-creates empty list
dd2 = defaultdict(int)
dd2["count"] += 1 # Auto-starts at 0
# --- Dict comprehension ---
squares = {x: x**2 for x in range(6)}
# --- Inverting a dict ---
inv = {v: k for k, v in d.items()}
# --- Sorting dict by value ---
sorted(d.items(), key=lambda x: x[1])
5. Comprehensions & Generators
# --- List comprehension ---
squares = [x**2 for x in range(10)]
evens = [x for x in range(20) if x % 2 == 0]
matrix = [[i * j for j in range(5)] for i in range(5)]
# --- Dict comprehension ---
word_len = {w: len(w) for w in ["hello", "world", "python"]}
# --- Set comprehension ---
unique_lens = {len(w) for w in ["hello", "world", "python"]}
# --- Generator expression — lazy, memory-efficient ---
gen = (x**2 for x in range(10)) # Does NOT compute yet
sum(x**2 for x in range(10)) # No brackets needed inside function call
# --- Generator function ---
def fibonacci():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
fib = fibonacci()
[next(fib) for _ in range(8)] # [0, 1, 1, 2, 3, 5, 8, 13]
# yield from — delegate to sub-generator
def chain(*iterables):
for it in iterables:
yield from it
# --- any() / all() with generators ---
any(x > 5 for x in [1, 2, 3, 6]) # True — short-circuits
all(x > 0 for x in [1, 2, 3, 4]) # True
6. Functions — Args, Kwargs, Closures, Decorators
# --- *args and **kwargs ---
def func(a, b, *args, **kwargs):
print(a, b) # Positional
print(args) # Tuple of extra positionals
print(kwargs) # Dict of extra keywords
func(1, 2, 3, 4, x=5, y=6)
# 1 2
# (3, 4)
# {'x': 5, 'y': 6}
# --- Keyword-only args (after *) ---
def func2(a, b, *, keyword_only):
pass
# --- Positional-only args (before /) ---
def func3(pos_only, /, normal, *, kw_only):
pass
# --- Default mutable argument gotcha ---
def append_to(elem, lst=[]): # WRONG! lst is created ONCE and shared
lst.append(elem)
return lst
def append_to_safe(elem, lst=None): # Correct pattern
if lst is None:
lst = []
lst.append(elem)
return lst
# --- Closures ---
def make_multiplier(n):
def multiplier(x):
return x * n # n is captured from enclosing scope
return multiplier
double = make_multiplier(2)
double(5) # 10
# --- Decorators ---
import functools
import time
def timer(func):
@functools.wraps(func) # Preserves __name__, __doc__
def wrapper(*args, **kwargs):
start = time.perf_counter()
result = func(*args, **kwargs)
end = time.perf_counter()
print(f"{func.__name__} took {end - start:.4f}s")
return result
return wrapper
@timer
def slow_function():
time.sleep(0.01)
# Decorator with arguments (factory pattern)
def retry(max_attempts=3):
def decorator(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
for attempt in range(max_attempts):
try:
return func(*args, **kwargs)
except Exception as e:
if attempt == max_attempts - 1:
raise
return None
return wrapper
return decorator
@retry(max_attempts=5)
def flaky_function():
pass
# --- Memoization decorator ---
from functools import lru_cache, cache
@lru_cache(maxsize=None) # Cache all results
def fib_cached(n):
if n < 2: return n
return fib_cached(n-1) + fib_cached(n-2)
@cache # Python 3.9+ shorthand for lru_cache(maxsize=None)
def fib_v2(n):
if n < 2: return n
return fib_v2(n-1) + fib_v2(n-2)
7. Object-Oriented Programming (OOP)
class Animal:
species_count = 0 # Class variable — shared across all instances
def __init__(self, name: str, age: int):
self.name = name # Instance variable
self.age = age
Animal.species_count += 1
def __repr__(self): # Unambiguous — for debugging, used by repr()
return f"Animal(name={self.name!r}, age={self.age})"
def __str__(self): # Human-readable — used by str() and print()
return f"{self.name} (age {self.age})"
def __eq__(self, other):
if not isinstance(other, Animal): return NotImplemented
return self.name == other.name and self.age == other.age
def __hash__(self): # Required if __eq__ is defined (to use in sets/dicts)
return hash((self.name, self.age))
def __lt__(self, other): # For sorting / comparisons
return self.age < other.age
def __len__(self):
return self.age
def speak(self): # Instance method
raise NotImplementedError
@classmethod
def create_puppy(cls, name): # Class method — receives class, not instance
return cls(name, 0)
@staticmethod
def is_valid_age(age): # Static method — no cls or self
return 0 <= age <= 150
@property
def description(self): # Property — accessed like attribute
return f"{self.name}, {self.age} years old"
@description.setter
def description(self, value):
# Custom setter logic
pass
class Dog(Animal):
def __init__(self, name, age, breed):
super().__init__(name, age) # Call parent __init__
self.breed = breed
def speak(self):
return f"{self.name} says Woof!"
def __repr__(self):
return f"Dog(name={self.name!r}, age={self.age}, breed={self.breed!r})"
# --- Abstract base classes ---
from abc import ABC, abstractmethod
class Shape(ABC):
@abstractmethod
def area(self) -> float:
pass
@abstractmethod
def perimeter(self) -> float:
pass
class Circle(Shape):
def __init__(self, radius: float):
self.radius = radius
def area(self) -> float:
return math.pi * self.radius ** 2
def perimeter(self) -> float:
return 2 * math.pi * self.radius
# --- Dataclasses (Python 3.7+) — auto-generates __init__, __repr__, __eq__ ---
from dataclasses import dataclass, field
@dataclass
class Point:
x: float
y: float
z: float = 0.0 # Default value
def distance_to_origin(self):
return (self.x**2 + self.y**2 + self.z**2) ** 0.5
@dataclass(order=True) # Also generates __lt__, __le__, etc.
class Employee:
sort_index: int = field(init=False, repr=False) # Not in __init__
name: str
salary: float
def __post_init__(self):
self.sort_index = self.salary # Set derived fields here
# --- __slots__ — memory optimization, also prevents adding new attributes ---
class Efficient:
__slots__ = ['x', 'y']
def __init__(self, x, y):
self.x = x
self.y = y
# --- Dunder methods summary ---
# __init__ Constructor
# __del__ Destructor
# __repr__ repr(obj) — for developers
# __str__ str(obj) — for users
# __len__ len(obj)
# __getitem__ obj[key]
# __setitem__ obj[key] = value
# __delitem__ del obj[key]
# __contains__ key in obj
# __iter__ iter(obj)
# __next__ next(obj)
# __call__ obj()
# __enter__ with obj as x:
# __exit__ end of with block
# __eq__, __lt__ ==, <
# __add__ obj + other
# __mul__ obj * other
# __bool__ bool(obj)
# __hash__ hash(obj)
8. Iterators & Itertools
import itertools
# --- Core itertools ---
# count(start, step) — infinite counter
# cycle(iterable) — infinite cycle
# repeat(obj, n) — repeat n times
list(itertools.accumulate([1, 2, 3, 4, 5])) # [1, 3, 6, 10, 15] — cumulative sum
list(itertools.accumulate([1, 2, 3, 4, 5], max)) # [1, 2, 3, 4, 5] running max
list(itertools.chain([1, 2], [3, 4], [5])) # [1, 2, 3, 4, 5]
list(itertools.combinations([1, 2, 3], 2))
# [(1,2), (1,3), (2,3)] — order doesn't matter, no repeats
list(itertools.combinations_with_replacement([1, 2], 2))
# [(1,1), (1,2), (2,2)]
list(itertools.permutations([1, 2, 3], 2))
# All ordered pairs
list(itertools.product([1, 2], [3, 4]))
# [(1,3), (1,4), (2,3), (2,4)] — cartesian product
list(itertools.product([0, 1], repeat=3))
# All 3-bit binary combos
list(itertools.islice(range(100), 5, 15, 2)) # [5, 7, 9, 11, 13]
list(itertools.groupby("AAABBBCCD"))
# [('A', iter), ('B', iter), ('C', iter), ('D', iter)]
# NOTE: Must be sorted first for meaningful grouping
list(itertools.starmap(pow, [(2, 3), (3, 2), (4, 2)])) # [8, 9, 16]
list(itertools.takewhile(lambda x: x < 5, [1, 2, 6, 2, 1])) # [1, 2]
list(itertools.dropwhile(lambda x: x < 5, [1, 2, 6, 2, 1])) # [6, 2, 1]
list(itertools.zip_longest([1, 2, 3], [4, 5], fillvalue=0))
# [(1,4), (2,5), (3,0)]
# --- enumerate and zip ---
for idx, val in enumerate(["a", "b", "c"], start=1):
print(idx, val)
for av, bv in zip([1, 2, 3], [4, 5, 6]):
print(av, bv)
# Unzip
pairs = [(1, 'a'), (2, 'b'), (3, 'c')]
nums, letters = zip(*pairs) # nums=(1,2,3), letters=('a','b','c')
9. Error Handling & Context Managers
# --- Exception hierarchy ---
# BaseException
# └── Exception
# ├── ValueError
# ├── TypeError
# ├── KeyError
# ├── IndexError
# ├── AttributeError
# ├── NameError
# ├── ZeroDivisionError
# ├── OverflowError
# ├── RuntimeError
# │ └── RecursionError
# ├── StopIteration
# ├── OSError
# │ ├── FileNotFoundError
# │ └── PermissionError
# └── ArithmeticError
# ├── ZeroDivisionError
# └── OverflowError
# --- try / except / else / finally ---
try:
result = 10 / 0
except ZeroDivisionError:
print("Divided by zero!")
except (TypeError, ValueError) as e:
print(f"Type or value error: {e}")
except Exception as e:
print(f"Unexpected: {e}")
raise # Re-raise the exception
else:
print("No exception occurred") # Only runs if try succeeded
finally:
print("Always runs") # Cleanup — always executes
# --- Custom exceptions ---
class InsufficientFundsError(ValueError):
def __init__(self, amount, balance):
super().__init__(f"Cannot withdraw {amount}, balance is {balance}")
self.amount = amount
self.balance = balance
# --- Context managers ---
# Using class-based __enter__ / __exit__
class ManagedResource:
def __enter__(self):
print("Acquiring resource")
return self
def __exit__(self, exc_type, exc_val, exc_tb):
print("Releasing resource")
return False # False = don't suppress exceptions
# Using contextlib
from contextlib import contextmanager
@contextmanager
def managed_resource():
print("Acquiring")
try:
yield "resource" # Value bound to `as` variable
finally:
print("Releasing")
with managed_resource() as r:
print(f"Using {r}")
10. File I/O
# --- Reading files ---
with open("file.txt", "r") as f:
content = f.read() # Entire file as string
# OR
lines = f.readlines() # List of lines (includes \n)
# OR
for line in f: # Memory-efficient iteration
line = line.strip()
# --- Writing files ---
with open("output.txt", "w") as f: # "w" overwrites, "a" appends
f.write("Hello\n")
f.writelines(["line1\n", "line2\n"])
# --- JSON ---
import json
data = {"key": "value", "num": 42}
json_str = json.dumps(data, indent=2)
parsed = json.loads(json_str)
with open("data.json", "w") as f:
json.dump(data, f)
with open("data.json", "r") as f:
data = json.load(f)
# --- CSV ---
import csv
with open("data.csv", "r") as f:
reader = csv.DictReader(f)
for row in reader:
print(row) # dict per row
# --- sys.stdin for competitive programming ---
import sys
input_data = sys.stdin.read().split()
# or: lines = sys.stdin.readlines()
11. Sorting, Searching, Custom Comparators
# --- sorted() vs list.sort() ---
lst = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_lst = sorted(lst) # Returns new list
lst.sort() # In-place, returns None
sorted(lst, reverse=True) # Descending
sorted(lst, key=lambda x: -x) # Equivalent
# --- Key function ---
words = ["banana", "apple", "cherry", "date"]
sorted(words, key=len) # By length
sorted(words, key=lambda w: (len(w), w)) # Multi-key: length, then alpha
# --- Sort objects ---
people = [("Alice", 30), ("Bob", 25), ("Charlie", 35)]
sorted(people, key=lambda p: p[1]) # By age
# --- functools.cmp_to_key — when you need a comparison function ---
import functools
def compare(a, b):
# Return negative if a < b, 0 if equal, positive if a > b
return a - b
sorted([3, 1, 4, 1, 5], key=functools.cmp_to_key(compare))
# Classic use: sort numbers to form the largest number
nums = [10, 9, 2, 45, 98]
def largest_number_cmp(a, b):
if a + b > b + a: return -1
elif a + b < b + a: return 1
return 0
nums_str = [str(n) for n in nums]
sorted(nums_str, key=functools.cmp_to_key(largest_number_cmp))
# --- min / max with key ---
max(words, key=len) # Longest word
min(people, key=lambda p: p[1]) # Youngest person
# --- bisect — binary search on sorted list ---
import bisect
a = [1, 3, 4, 7, 10]
bisect.bisect_left(a, 4) # 2 — leftmost position to insert 4
bisect.bisect_right(a, 4) # 3 — rightmost position to insert 4
bisect.insort_left(a, 5) # Insert in sorted order
# Count elements < target
def count_less_than(a, target):
return bisect.bisect_left(a, target)
# Count elements in [lo, hi]
def count_in_range(a, lo, hi):
return bisect.bisect_right(a, hi) - bisect.bisect_left(a, lo)
12. Bit Manipulation
# --- Operators ---
# & AND 5 & 3 -> 1 (0101 & 0011 = 0001)
# | OR 5 | 3 -> 7 (0101 | 0011 = 0111)
# ^ XOR 5 ^ 3 -> 6 (0101 ^ 0011 = 0110)
# ~ NOT ~5 -> -6 (inverts all bits, ~n = -(n+1))
# << Left shift 1 << 3 -> 8 (multiply by 2^3)
# >> Right shift 8 >> 2 -> 2 (floor divide by 2^2)
# --- Common bit tricks ---
n = 42
n & 1 # Check if odd (last bit)
n | 1 # Set last bit (make odd)
n & ~1 # Clear last bit (make even)
n ^ n # 0 — XOR with itself
# Get bit i
(n >> i) & 1
# Set bit i
n | (1 << i)
# Clear bit i
n & ~(1 << i)
# Toggle bit i
n ^ (1 << i)
# Check power of 2
n > 0 and (n & (n - 1)) == 0
# Remove lowest set bit (Brian Kernighan's trick)
n & (n - 1)
# Extract lowest set bit
n & (-n)
# Count set bits (popcount)
bin(n).count('1')
n.bit_count() # Python 3.10+
# Swap without temp
a, b = 5, 3
a ^= b; b ^= a; a ^= b
# XOR trick: find the unique number where all others appear twice
nums = [1, 2, 3, 2, 1]
result = 0
for num in nums:
result ^= num # result = 3
# --- int to binary string and back ---
bin(42) # '0b101010'
bin(42)[2:] # '101010'
int('101010', 2) # 42
format(42, '08b') # '00101010' (8-bit, zero-padded)
# --- Python has arbitrary precision ints — no overflow! ---
# But: ~n = -(n+1), and right shift of negative fills with 1 (arithmetic shift)
# To simulate 32-bit: use mask = 0xFFFFFFFF
13. Collections Module
from collections import Counter, defaultdict, deque, OrderedDict, namedtuple, ChainMap
# --- Counter ---
c = Counter("abracadabra") # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
c.most_common(2) # [('a', 5), ('b', 2)]
c["z"] # 0 — doesn't raise KeyError!
c + Counter("aaa") # Add counts
c - Counter("aaa") # Subtract (drops negatives)
c.elements() # Iterator of elements with their counts
sum(c.values()) # Total count
# --- deque (double-ended queue) ---
# O(1) append/pop from both ends; O(n) access by index
dq = deque([1, 2, 3])
dq.append(4) # Right end
dq.appendleft(0) # Left end
dq.pop() # Remove right
dq.popleft() # Remove left — this is what makes it O(1) vs list!
dq.rotate(2) # Rotate right by 2
dq.rotate(-2) # Rotate left by 2
deque([1, 2, 3], maxlen=3) # Fixed-size sliding window
# --- OrderedDict ---
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od.move_to_end('a') # Move to last
od.move_to_end('a', last=False) # Move to first
od.popitem(last=True) # LIFO pop
od.popitem(last=False) # FIFO pop
# --- ChainMap — combine dicts, lookups search all ---
defaults = {'color': 'red', 'size': 'M'}
overrides = {'color': 'blue'}
combined = ChainMap(overrides, defaults)
combined['color'] # 'blue' — from overrides
combined['size'] # 'M' — from defaults
14. Heapq & Priority Queues
import heapq
# Python's heapq is a MIN-heap
# To simulate MAX-heap: negate values
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums) # In-place: O(n)
heapq.heappush(nums, 0) # O(log n)
smallest = heapq.heappop(nums) # O(log n) — removes and returns smallest
nums[0] # Peek at smallest: O(1) (don't pop!)
heapq.heappushpop(nums, 7) # Push then pop (more efficient than separate calls)
heapq.heapreplace(nums, 7) # Pop then push (heap must be non-empty)
heapq.nsmallest(3, nums) # 3 smallest: O(n log k)
heapq.nlargest(3, nums) # 3 largest: O(n log k)
# --- Max-heap pattern ---
max_heap = [-x for x in [3, 1, 4, 1, 5, 9]]
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap) # 9
# --- Heap with custom key (tuples) ---
# Heap compares element by element: (priority, data)
tasks = [(3, "low priority"), (1, "urgent"), (2, "medium")]
heapq.heapify(tasks)
priority, task = heapq.heappop(tasks) # (1, "urgent")
# When data is not comparable, use (priority, counter, data) to break ties
from itertools import count
unique = count()
pq = []
heapq.heappush(pq, (1, next(unique), "task_a"))
heapq.heappush(pq, (1, next(unique), "task_b")) # Counter breaks tie
# --- K Largest Elements ---
def k_largest(nums, k):
return heapq.nlargest(k, nums)
# --- K Smallest using max-heap of size k ---
def k_smallest_heap(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, -num)
if len(heap) > k:
heapq.heappop(heap)
return [-x for x in heap]
# --- Merge K sorted lists ---
def merge_k_sorted(lists):
result = []
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
nxt = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (nxt, list_idx, elem_idx + 1))
return result
15. Functional Programming
from functools import reduce
# --- lambda ---
square = lambda x: x ** 2
add = lambda x, y: x + y
# --- map / filter / reduce ---
list(map(str, [1, 2, 3])) # ['1', '2', '3']
list(map(lambda x: x*2, [1, 2, 3])) # [2, 4, 6]
list(filter(lambda x: x % 2, [1,2,3,4])) # [1, 3] — odd numbers
reduce(lambda acc, x: acc + x, [1,2,3,4,5], 0) # 15
# Prefer comprehensions over map/filter in most cases (more Pythonic)
# Use map/filter when working with existing functions:
list(map(int, "12345")) # [1, 2, 3, 4, 5]
list(map(abs, [-1, -2, 3])) # [1, 2, 3]
# --- partial functions ---
from functools import partial
def power(base, exp):
return base ** exp
square = partial(power, exp=2)
cube = partial(power, exp=3)
square(5) # 25
cube(3) # 27
# --- operator module (avoid lambdas for simple ops) ---
import operator
operator.add(1, 2) # 3
operator.itemgetter(1)([1, 2, 3]) # 2 — useful for sorting
operator.attrgetter('age')
sorted(people, key=operator.itemgetter(1)) # Sort by second element
16. Recursion & Memoization
import sys
sys.setrecursionlimit(10**6) # Default is 1000 — increase for deep recursion
# --- Classic recursion patterns ---
# Factorial
def factorial(n):
if n <= 1: return 1
return n * factorial(n - 1)
# Power (fast exponentiation)
def power(base, exp):
if exp == 0: return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half
return base * power(base, exp - 1)
# --- Memoization — top-down DP ---
# Option 1: lru_cache decorator
@lru_cache(maxsize=None)
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
# Option 2: Manual memo dict
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n < 2: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# Option 3: Pass memo explicitly (avoids mutable default gotcha)
def fib_clean(n, memo=None):
if memo is None: memo = {}
if n in memo: return memo[n]
if n < 2: return n
memo[n] = fib_clean(n-1, memo) + fib_clean(n-2, memo)
return memo[n]
# --- Recursion to iteration (using explicit stack) ---
def tree_traversal_iterative(root):
stack = [root]
result = []
while stack:
node = stack.pop()
if node:
result.append(node.val)
stack.append(node.right)
stack.append(node.left)
return result
17. Dynamic Programming Patterns
# --- 1. Fibonacci / linear DP ---
def fib_dp(n):
if n < 2: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# --- 2. 0/1 Knapsack ---
def knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1): # Iterate backwards!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# --- 3. Unbounded Knapsack (Coin Change) ---
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for amt in range(1, amount + 1):
for coin in coins:
if coin <= amt:
dp[amt] = min(dp[amt], dp[amt - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# --- 4. Longest Common Subsequence (LCS) ---
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# --- 5. Longest Increasing Subsequence (LIS) — O(n log n) ---
def lis(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
# --- 6. Edit Distance ---
def edit_distance(s, t):
m, n = len(s), len(t)
dp = list(range(n + 1))
for i in range(1, m + 1):
new_dp = [i] + [0] * n
for j in range(1, n + 1):
if s[i-1] == t[j-1]:
new_dp[j] = dp[j-1]
else:
new_dp[j] = 1 + min(dp[j], new_dp[j-1], dp[j-1])
dp = new_dp
return dp[n]
# --- 7. Max Subarray — Kadane's Algorithm ---
def max_subarray(nums):
max_sum = curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
# --- 8. House Robber pattern ---
def house_robber(nums):
if not nums: return 0
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
# --- 9. 2D DP — Unique Paths ---
def unique_paths(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[n-1]
# --- 10. DP on intervals — Burst Balloons ---
def max_coins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(0, n - length):
right = left + length
for k in range(left + 1, right):
dp[left][right] = max(
dp[left][right],
nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
)
return dp[0][n-1]
# --- DP Tips ---
# 1. Define dp[i] clearly: "dp[i] = max profit using first i items"
# 2. Base cases: empty input, single element
# 3. Space optimization: often 2D -> 1D (rolling array)
# 4. Top-down (memoization) vs bottom-up (tabulation)
# 5. Common patterns: subsequence, subarray, partition, interval, state machine
18. Graph Algorithms
from collections import deque
# --- Graph representations ---
# Adjacency list (most common)
graph = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
3: [1],
4: [2]
}
# Adjacency list with weights
weighted = {
0: [(1, 4), (2, 1)], # (neighbor, weight)
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: []
}
# --- BFS ---
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# BFS shortest path
def bfs_shortest(graph, start, end):
visited = {start: None} # node -> parent
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
path = []
while node is not None:
path.append(node)
node = visited[node]
return path[::-1]
for neighbor in graph[node]:
if neighbor not in visited:
visited[neighbor] = node
queue.append(neighbor)
return [] # No path
# --- DFS (iterative) ---
def dfs_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return order
# --- DFS (recursive) ---
def dfs_recursive(graph, node, visited=None):
if visited is None: visited = set()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
# --- Detect cycle in undirected graph (DFS) ---
def has_cycle_undirected(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node): return True
elif neighbor != parent:
return True # Back edge found
return False
for node in graph:
if node not in visited:
if dfs(node, -1): return True
return False
# --- Topological Sort (Kahn's algorithm — BFS) ---
def topo_sort_kahn(n, edges):
in_degree = [0] * n
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else [] # Empty = cycle exists
# --- Topological Sort (DFS) ---
def topo_sort_dfs(graph):
visited, stack = set(), []
def dfs(node):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1]
# --- Dijkstra's Algorithm (shortest path, non-negative weights) ---
def dijkstra(graph, start):
dist = defaultdict(lambda: float('inf'))
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]: continue # Stale entry
for neighbor, weight in graph[node]:
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
# --- Union-Find (Disjoint Set Union) ---
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False # Already connected
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.components -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# --- Number of Islands (BFS on grid) ---
def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def bfs(r, c):
queue = deque([(r, c)])
grid[r][c] = '0'
while queue:
row, col = queue.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
bfs(r, c)
count += 1
return count
# --- Bellman-Ford (handles negative edges) ---
def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # Negative cycle exists
return dist
# --- Directions for 2D grid problems ---
DIRS_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, down, left, right
DIRS_8 = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] # All 8
def in_bounds(r, c, rows, cols):
return 0 <= r < rows and 0 <= c < cols
19. Tree Algorithms
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
return f"TreeNode({self.val})"
# --- Build tree from level-order list ---
def build_tree(values):
if not values or values[0] is None: return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# --- Traversals ---
def inorder(root): # Left -> Root -> Right (gives sorted BST)
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root): # Root -> Left -> Right
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root): # Left -> Right -> Root
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
# Iterative inorder (important!)
def inorder_iterative(root):
stack, result = [], []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
# Level-order (BFS)
def level_order(root):
if not root: return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
# --- Tree properties ---
def height(root):
if not root: return 0
return 1 + max(height(root.left), height(root.right))
def is_balanced(root):
def check(node):
if not node: return 0
left = check(node.left)
if left == -1: return -1
right = check(node.right)
if right == -1: return -1
if abs(left - right) > 1: return -1
return 1 + max(left, right)
return check(root) != -1
def diameter(root):
result = [0]
def depth(node):
if not node: return 0
left, right = depth(node.left), depth(node.right)
result[0] = max(result[0], left + right)
return 1 + max(left, right)
depth(root)
return result[0]
# --- BST operations ---
def bst_search(root, val):
if not root or root.val == val: return root
if val < root.val: return bst_search(root.left, val)
return bst_search(root.right, val)
def bst_insert(root, val):
if not root: return TreeNode(val)
if val < root.val: root.left = bst_insert(root.left, val)
elif val > root.val: root.right = bst_insert(root.right, val)
return root
def bst_inorder_successor(root, target):
successor = None
while root:
if target.val < root.val:
successor = root
root = root.left
else:
root = root.right
return successor
# --- LCA (Lowest Common Ancestor) ---
def lca(root, p, q):
if not root or root == p or root == q: return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right: return root # p and q on different sides
return left or right
# LCA for BST (more efficient):
def lca_bst(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
20. Linked List Patterns
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def make_list(values):
dummy = ListNode(0)
curr = dummy
for v in values:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# --- Reverse linked list (iterative) ---
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
# --- Reverse linked list (recursive) ---
def reverse_recursive(head):
if not head or not head.next: return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# --- Detect cycle (Floyd's algorithm) ---
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True
return False
def find_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
# --- Middle of linked list ---
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# --- Merge two sorted lists ---
def merge_sorted(l1, l2):
dummy = curr = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
# --- Remove Nth node from end ---
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
# --- Palindrome linked list ---
def is_palindrome_list(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next; curr.next = prev; prev = curr; curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val: return False
left = left.next; right = right.next
return True
21. Sliding Window & Two Pointers
# --- Fixed-size sliding window ---
def max_sum_subarray(nums, k):
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# --- Variable-size sliding window ---
# Template:
def sliding_window_variable(nums, target):
left = 0
window_state = 0 # Could be sum, count, dict, etc.
result = 0
for right in range(len(nums)):
window_state += nums[right] # Expand window
while window_state > target: # Shrink condition
window_state -= nums[left]
left += 1
result = max(result, right - left + 1)
return result
# Longest substring without repeating characters
def length_of_longest_substring(s):
char_count = {}
left = 0
max_len = 0
for right, ch in enumerate(s):
char_count[ch] = char_count.get(ch, 0) + 1
while char_count[ch] > 1:
char_count[s[left]] -= 1
if char_count[s[left]] == 0:
del char_count[s[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
# Minimum window substring
def min_window(s, t):
need = Counter(t)
missing = len(t)
best = ""
left = 0
for right, ch in enumerate(s):
if need[ch] > 0: missing -= 1
need[ch] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if not best or right - left + 1 < len(best):
best = s[left:right+1]
need[s[left]] += 1
missing += 1
left += 1
return best
# --- Two pointers ---
# Two sum (sorted array)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []
# Container with most water
def max_water(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)
if height[left] < height[right]: left += 1
else: right -= 1
return max_area
# 3Sum
def three_sum(nums):
nums.sort()
result = []
for i, a in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]: continue
left, right = i + 1, len(nums) - 1
while left < right:
s = a + nums[left] + nums[right]
if s == 0:
result.append([a, nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
22. Binary Search Patterns
# --- Classic binary search ---
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoids overflow (critical in other languages)
if nums[mid] == target: return mid
elif nums[mid] < target: left = mid + 1
else: right = mid - 1
return -1
# --- Find leftmost position (lower bound) ---
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target: left = mid + 1
else: right = mid
return left # First index where nums[i] >= target
# --- Find rightmost position (upper bound) ---
def upper_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] <= target: left = mid + 1
else: right = mid
return left - 1 # Last index where nums[i] <= target
# --- Binary search on answer (search space) ---
# Template: "find minimum X such that condition(X) is True"
def binary_search_answer(lo, hi, condition):
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid
else:
lo = mid + 1
return lo
# Example: Koko eating bananas
def min_eating_speed(piles, h):
def can_finish(speed):
return sum(math.ceil(p / speed) for p in piles) <= h
return binary_search_answer(1, max(piles), can_finish)
# Example: Minimum capacity to ship packages
def ship_capacity(weights, days):
def can_ship(cap):
d, curr = 1, 0
for w in weights:
if curr + w > cap: d += 1; curr = 0
curr += w
return d <= days
return binary_search_answer(max(weights), sum(weights), can_ship)
# --- Search in rotated sorted array ---
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return mid
if nums[left] <= nums[mid]: # Left half is sorted
if nums[left] <= target < nums[mid]: right = mid - 1
else: left = mid + 1
else: # Right half is sorted
if nums[mid] < target <= nums[right]: left = mid + 1
else: right = mid - 1
return -1
# --- Find peak element ---
def find_peak(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[mid + 1]: right = mid
else: left = mid + 1
return left
23. Stack & Queue Patterns
# --- Monotonic stack ---
# Useful for: next greater/smaller element, histogram problems
# Next Greater Element
def next_greater_element(nums):
result = [-1] * len(nums)
stack = [] # Stores indices
for i, n in enumerate(nums):
while stack and nums[stack[-1]] < n:
result[stack.pop()] = n
stack.append(i)
return result
# Largest Rectangle in Histogram
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0] # Sentinel to flush stack
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
idx, height = stack.pop()
max_area = max(max_area, height * (i - idx))
start = idx
stack.append((start, h))
return max_area
# Trapping Rain Water (monotonic stack OR two pointers)
def trap_rain(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max: left_max = height[left]
else: water += left_max - height[left]
left += 1
else:
if height[right] >= right_max: right_max = height[right]
else: water += right_max - height[right]
right -= 1
return water
# Daily Temperatures (next greater using stack)
def daily_temps(temps):
result = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
# --- Valid parentheses ---
def is_valid_parens(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '({[': stack.append(ch)
elif not stack or stack[-1] != pairs[ch]: return False
else: stack.pop()
return len(stack) == 0
# --- Queue using two stacks ---
class MyQueue:
def __init__(self):
self.in_stack, self.out_stack = [], []
def push(self, x):
self.in_stack.append(x)
def pop(self):
self._transfer()
return self.out_stack.pop()
def peek(self):
self._transfer()
return self.out_stack[-1]
def _transfer(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
# --- Min Stack ---
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
min_val = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(min_val)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def get_min(self):
return self.min_stack[-1]
24. Backtracking
# Template:
# def backtrack(state, choices):
# if base_case(state):
# result.append(state.copy())
# return
# for choice in choices:
# if is_valid(choice, state):
# make_choice(state, choice)
# backtrack(state, updated_choices)
# undo_choice(state, choice) <- KEY: restore state
# --- Permutations ---
def permutations(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i, n in enumerate(remaining):
path.append(n)
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return result
# --- Subsets ---
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# --- Combination Sum (unlimited use) ---
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i (not i+1) for reuse
path.pop()
candidates.sort()
backtrack(0, [], target)
return result
# --- N-Queens ---
def solve_n_queens(n):
result = []
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row, board):
if row == n:
result.append(["".join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
board[row][col] = 'Q'
backtrack(row + 1, board)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
board[row][col] = '.'
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(0, board)
return result
# --- Word Search ---
def word_search(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word): return True
if not (0 <= r < rows) or not (0 <= c < cols): return False
if board[r][c] != word[idx]: return False
tmp, board[r][c] = board[r][c], '#'
found = any(dfs(r+dr, c+dc, idx+1) for dr, dc in DIRS_4)
board[r][c] = tmp
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
25. Greedy Algorithms
# Greedy works when: local optimal choices lead to global optimum.
# Key: Think about what invariant you're maintaining.
# --- Activity Selection / Interval Scheduling ---
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1]) # Sort by end time
count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
# --- Merge Intervals ---
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# --- Jump Game ---
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: return False
max_reach = max(max_reach, i + jump)
return True
def min_jumps(nums):
jumps = farthest = curr_end = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == curr_end:
jumps += 1
curr_end = farthest
return jumps
# --- Gas Station ---
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost): return -1
tank = start = 0
for i, (g, c) in enumerate(zip(gas, cost)):
tank += g - c
if tank < 0:
start = i + 1
tank = 0
return start
# --- Task Scheduler ---
def task_scheduler(tasks, n):
counts = Counter(tasks)
max_freq = max(counts.values())
max_count = sum(1 for v in counts.values() if v == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)
26. Complexity Cheat Sheet
"""
DATA STRUCTURE COMPLEXITIES
─────────────────────────────────────────────────────────────────────────────
Access Search Insert Delete Space
─────────────────────────────────────────────────────────────────────────────
Array (list) O(1) O(n) O(n) O(n) O(n)
list.append/pop() O(1)* - O(1)* O(1)* -
dict / set O(1)* O(1)* O(1)* O(1)* O(n)
Sorted dict/set - O(log n) O(log n) O(log n) O(n)
Heap (heapq) O(1)peek O(n) O(log n) O(log n) O(n)
deque append/pop O(1) O(n) O(1) O(1) O(n)
Linked list O(n) O(n) O(1)head O(1)head O(n)
BST (balanced) O(log n) O(log n) O(log n) O(log n) O(n)
Trie O(m) O(m) O(m) O(m) O(ALPHABET*n)
* = amortized
ALGORITHM COMPLEXITIES
─────────────────────────────────────────────────────────────────────────────
Binary Search O(log n)
Sorting (comparison) O(n log n) — lower bound for comparison sort
Counting Sort O(n + k) — k is range of values
BFS / DFS O(V + E)
Dijkstra (heap) O((V+E) log V)
Bellman-Ford O(VE)
Floyd-Warshall O(V^3)
Topological Sort O(V+E)
Union-Find O(α(n)) ≈ O(1) amortized with path compression
Knapsack (0/1) O(n * W)
LCS O(m * n)
Matrix Multiply O(n^3) naive, O(n^2.37) Strassen
PYTHON-SPECIFIC
─────────────────────────────────────────────────────────────────────────────
len(list/dict/str) O(1)
x in list O(n) <- Use set for O(1) lookup!
x in set/dict O(1)
list slicing [i:j] O(j-i)
list concatenation O(n)
"".join(list) O(n) <- Always use join, not +=
sorted() O(n log n)
list.sort() O(n log n) Timsort (stable, adaptive)
heapq.heapify O(n)
Counter(iterable) O(n)
"""
27. Python-Specific Tricks
# --- String building: always join, never += in a loop ---
# Slow — creates a new string each iteration: O(n^2)
result = ""
for c in "hello":
result += c
# Fast — O(n)
result = "".join(["h", "e", "l", "l", "o"])
# --- Check if all chars are unique ---
def all_unique(s):
return len(s) == len(set(s))
# --- Most frequent element ---
def most_frequent(nums):
return Counter(nums).most_common(1)[0][0]
# --- Rotate list ---
def rotate(nums, k):
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k] # In-place with slice assignment
# --- Group anagrams ---
def group_anagrams(strs):
d = defaultdict(list)
for s in strs:
d[tuple(sorted(s))].append(s)
return list(d.values())
# --- Flatten nested structure (iterative) ---
def flatten(lst):
stack = lst[::-1]
result = []
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(item[::-1])
else:
result.append(item)
return result
# --- Prefix sums for range queries ---
def range_sum_setup(nums):
prefix = [0] * (len(nums) + 1)
for i, n in enumerate(nums):
prefix[i+1] = prefix[i] + n
def query(l, r): # Sum of nums[l..r] inclusive
return prefix[r+1] - prefix[l]
return query
# --- Difference array for range updates ---
def range_add(nums, updates):
diff = [0] * (len(nums) + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
curr = 0
for i in range(len(nums)):
curr += diff[i]
nums[i] += curr
return nums
# --- Two-pointer partition (Dutch National Flag) ---
def dutch_flag(nums):
lo, mid, hi = 0, 0, len(nums) - 1
while mid <= hi:
if nums[mid] == 0:
nums[lo], nums[mid] = nums[mid], nums[lo]
lo += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[hi] = nums[hi], nums[mid]
hi -= 1
return nums
# --- Fast I/O for competitive programming ---
# input = sys.stdin.readline # Faster than built-in input()
# print = sys.stdout.write # Use sys.stdout.write(str + "\n")
# --- Integer sqrt without import ---
def isqrt(n):
if n < 0: raise ValueError
x = int(n ** 0.5)
while x * x > n: x -= 1
while (x + 1) * (x + 1) <= n: x += 1
return x
# Python 3.8+: math.isqrt(n)
# --- GCD and LCM ---
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
# Python 3.9+: math.lcm(a, b)
# --- Useful math ---
import math
math.ceil(7/2) # 4
math.floor(7/2) # 3
round(2.5) # 2 (banker's rounding!) round(3.5)=4
math.log2(8) # 3.0
math.log(100, 10) # 2.0
# --- All prime numbers up to n (Sieve of Eratosthenes) ---
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(2, n+1) if is_prime[i]]
# --- Check prime ---
def is_prime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0: return False
return True
# --- Trie data structure ---
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children: return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True
# --- Segment Tree (range query + point update) ---
class SegmentTree:
def __init__(self, nums):
n = len(nums)
self.n = n
self.tree = [0] * (2 * n)
self.tree[n:] = nums
for i in range(n - 1, 0, -1):
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def update(self, pos, val):
pos += self.n
self.tree[pos] = val
while pos > 1:
pos //= 2
self.tree[pos] = self.tree[2*pos] + self.tree[2*pos+1]
def query(self, l, r): # Sum of [l, r)
l += self.n; r += self.n
result = 0
while l < r:
if l & 1: result += self.tree[l]; l += 1
if r & 1: r -= 1; result += self.tree[r]
l >>= 1; r >>= 1
return result
# --- Binary Indexed Tree (Fenwick Tree) — simpler range sum ---
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta): # 1-indexed
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def query(self, i): # Prefix sum [1..i]
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
def range_query(self, l, r): # Sum [l..r]
return self.query(r) - self.query(l - 1)
# --------
# Testing in Python
# --------
# 1. The function you want to test
def add(a, b):
return a + b
# 2. The test block
if __name__ == "__main__":
# Test 1: Positive numbers
assert add(2, 3) == 5, "Test 1 failed: Expected 5"
# Test 2: Negative numbers
assert add(-1, -1) == -2, "Test 2 failed: Expected -2"
print("All tests passed!")
28. Common Patterns Summary
"""
PATTERN RECOGNITION GUIDE
─────────────────────────────────────────────────────────────────────────────
SIGNAL PATTERN TO CONSIDER
─────────────────────────────────────────────────────────────────────────────
"Top K" / "K largest/smallest" Heap (min or max)
"K closest" Heap with distance key
Sorted array + target Binary Search / Two Pointers
"Subarray sum = k" Prefix Sum + HashMap
"Longest subarray / substring" Sliding Window
"All permutations / subsets" Backtracking
"Optimal choices at each step" Greedy or DP
"Overlapping subproblems" DP (top-down memo or bottom-up)
"Next greater / smaller element" Monotonic Stack
"Islands / connected components" BFS/DFS on grid
"Shortest path (unweighted)" BFS
"Shortest path (weighted)" Dijkstra / Bellman-Ford
"Course prerequisites / ordering" Topological Sort
"Union / Find groups" Union-Find (DSU)
"Word prefix / autocomplete" Trie
"Range sum queries" Prefix Sum / Segment Tree / BIT
"Linked list cycle / middle" Floyd's Slow/Fast Pointer
"Tree path / ancestor" DFS / LCA
"Bracket matching" Stack
"Rotated array" Binary Search (modified)
"Matrix search" Binary Search / BFS
DECISION TREE FOR DP
─────────────────────────────────────────────────────────────────────────────
1. Can I define subproblem as a suffix/prefix of input? -> 1D DP (array)
2. Does it involve two sequences? -> 2D DP (LCS, Edit Distance)
3. Is it about choosing items with a budget/capacity? -> Knapsack
4. Does the problem involve a range [i..j]? -> Interval DP
5. Does it involve a state machine / transitions? -> State DP
6. Does the recursion tree have repeated subproblems? -> Memoize it
COMMON COMPLEXITY TARGETS
─────────────────────────────────────────────────────────────────────────────
n ≤ 10: O(n!) — backtracking / all perms OK
n ≤ 20: O(2^n) — bitmask DP / subset enumeration
n ≤ 500: O(n^3) — Floyd-Warshall, interval DP
n ≤ 5000: O(n^2) — 2D DP, brute force nested loops
n ≤ 10^6: O(n log n) — sorting, heap, BFS/DFS
n ≤ 10^8: O(n) — linear pass, prefix sum, hash
n > 10^8: O(log n) or O(1) — binary search, math
CODING APPROACH
─────────────────────────────────────────────────────────────────────────────
1. Clarify: input size, edge cases, return type, constraints
2. Examples: walk through 2-3 examples including edge cases
3. Brute force: state it first, then optimize
4. Pattern: identify which paradigm applies
5. Complexity: analyze time and space before coding
6. Code: clean, readable, use helper functions
7. Test: trace through your examples, check edge cases
EDGE CASES TO ALWAYS CONSIDER
─────────────────────────────────────────────────────────────────────────────
[ ] Empty input ([], "", None, 0)
[ ] Single element
[ ] All same elements
[ ] Negative numbers / zero
[ ] Already sorted / reverse sorted
[ ] Overflow (Python ints are safe, but simulate 32-bit if asked)
[ ] Disconnected graph / forest
[ ] Null tree root
[ ] Cycle in linked list / graph
"""