Other Algorithmic Paradigms¶
This chapter covers essential algorithmic paradigms beyond the core Dynamic Programming, Greedy, Graph, Searching, and Sorting algorithms. These techniques form the foundation for solving complex combinatorial, string, geometric, and optimization problems.
1. Backtracking: Exhaustive Pruned Search in Decision Trees¶
Backtracking is a powerful algorithmic paradigm for solving combinatorial problems by systematically exploring the solution space through a decision tree, incrementally building partial candidates and abandoning (backtracking) branches that violate constraints or prove suboptimal. It transforms brute-force enumeration—often exponential O(b^d) where b is branching factor and d is depth—into a pruned search, leveraging domain reduction and validity checks to make otherwise intractable problems feasible.
Rooted in constraint satisfaction and search theory (e.g., AI planning), backtracking models problems as CSPs (Constraint Satisfaction Problems): Assign variables from domains subject to constraints. Unlike DP (memoizes subproblems for optimality), backtracking enumerates but prunes early, succeeding when constraints are tight. Theoretical depth: Worst-case still exponential, but average polynomial via pruning ratio; integrates with branch-and-bound for optimization.
1.1 Core Mechanics¶
Backtracking performs a depth-first search (DFS) on a decision tree, where each level corresponds to a variable, branches to domain values, and nodes to partial assignments. Pruning occurs when a partial fails constraints, avoiding subtree explosion.
-
Decision Tree Structure:
- Root: Empty assignment.
- Levels: Variable order (e.g., row 1 to n in N-Queens).
- Branches: Domain values (e.g., columns 0 to n-1).
- Leaves: Full assignments (solutions or invalid).
-
State Management:
- Partial Assignment: Array/state vector (e.g.,
board[row] = col). - Domains: Sets per variable (initial full; reduced via propagation).
- Constraints: Unary/binary/arity-k checks (e.g., no diagonal attacks).
- Stack/Recursion: Tracks path (depth d max).
- Partial Assignment: Array/state vector (e.g.,
-
Phases (Choose-Constrain-Recurse-Unchoose):
- Choose: Select unassigned variable (e.g., next row); try domain value.
- Constrain: Validate partial (check conflicts with priors); prune if invalid.
- Recurse: If valid and not complete, advance to next variable.
- Unchoose: Restore state (remove assignment) after subtree exploration.
-
Key Invariant: All explored partials are consistent (no prior violations).
- Termination: All variables assigned (solution) or no domains left (fail).
Generic CSP Backtracking Template:
def backtrack(assignment: dict, variables: list, domains: dict) -> list:
"""
Generic backtracking for Constraint Satisfaction Problems.
Returns list of all valid complete assignments.
"""
solutions = []
def solve():
# Base case: all variables assigned
if len(assignment) == len(variables):
solutions.append(assignment.copy())
return
# Select unassigned variable (MRV heuristic: smallest domain first)
var = select_variable(variables, assignment, domains)
# Try each value in domain (LCV heuristic: least constraining first)
for val in order_domain_values(var, domains):
if is_consistent(assignment, var, val):
# Choose
assignment[var] = val
removed = forward_check(domains, var, val)
# Recurse
solve()
# Unchoose (backtrack)
del assignment[var]
restore_domains(domains, removed)
solve()
return solutions
def is_consistent(assignment: dict, var, val) -> bool:
"""Check if assigning val to var violates any constraint."""
for other_var, other_val in assignment.items():
if not satisfies_constraint(var, val, other_var, other_val):
return False
return True
def select_variable(variables, assignment, domains):
"""MRV: Choose variable with minimum remaining values."""
unassigned = [v for v in variables if v not in assignment]
return min(unassigned, key=lambda v: len(domains[v]))
def forward_check(domains, var, val):
"""Propagate constraints: remove inconsistent values from other domains."""
removed = {}
for other_var in domains:
if other_var == var:
continue
to_remove = []
for other_val in domains[other_var]:
if not satisfies_constraint(var, val, other_var, other_val):
to_remove.append(other_val)
if to_remove:
removed[other_var] = to_remove
for v in to_remove:
domains[other_var].remove(v)
return removed
1.2 Complexity Analysis¶
Backtracking's time reflects explored tree size, pruned by constraint tightness.
| Scenario | Time | Space | Derivation |
|---|---|---|---|
| Worst (Loose Constraints) | O(b^d) | O(d) stack | Full enumeration |
| Average (Tight Prune r=0.5) | O(b^{d/2}) | O(d) | Half branches viable |
| With Forward Check | O(b^{d(1-log r)}) | O(d + domains) | Propagation prunes more |
- Space Complexity: O(d) for recursion stack + O(V × D) for domain copies where V = number of variables, D = average domain size.
1.3 Variable and Value Ordering Heuristics¶
Effective ordering dramatically reduces search space:
| Heuristic | Type | Strategy | Effect |
|---|---|---|---|
| MRV (Minimum Remaining Values) | Variable | Choose variable with smallest domain | Fail-fast: detect dead-ends early |
| Degree | Variable | Choose variable involved in most constraints | Maximize propagation impact |
| LCV (Least Constraining Value) | Value | Choose value that rules out fewest choices for neighbors | Maximize future flexibility |
1.4 Constraint Propagation: Arc Consistency (AC-3)¶
AC-3 enforces arc consistency before and during search, eliminating values that cannot participate in any solution.
from collections import deque
def ac3(domains: dict, constraints: dict) -> bool:
"""
AC-3 algorithm for arc consistency.
constraints: dict mapping (var1, var2) -> constraint_function
Returns False if domain becomes empty (no solution exists).
Time: O(ed³) where e = #constraints, d = max domain size
"""
# Initialize queue with all arcs
queue = deque()
for (xi, xj) in constraints:
queue.append((xi, xj))
queue.append((xj, xi)) # Both directions
while queue:
(xi, xj) = queue.popleft()
if revise(domains, xi, xj, constraints):
if not domains[xi]:
return False # Domain wiped out
# Add all arcs (xk, xi) where xk != xj
for xk in domains:
if xk != xi and xk != xj:
queue.append((xk, xi))
return True
def revise(domains, xi, xj, constraints) -> bool:
"""Remove values from domains[xi] with no support in domains[xj]."""
revised = False
constraint = constraints.get((xi, xj)) or constraints.get((xj, xi))
for vi in list(domains[xi]):
# Check if any value in xj's domain satisfies constraint
if not any(constraint(vi, vj) for vj in domains[xj]):
domains[xi].remove(vi)
revised = True
return revised
1.5 Classic Examples¶
N-Queens: Non-Attacking Queens on Chessboard¶
Place n queens on an n×n board such that no two attack each other.
def solve_n_queens(n: int) -> list[list[str]]:
"""
Solve N-Queens problem using backtracking with constraint sets.
Time: O(n!) worst case, much faster with pruning
Space: O(n) for board state + O(n) for constraint sets
"""
solutions = []
board = [-1] * n # board[row] = column of queen
# Constraint sets for O(1) conflict checking
cols = set() # Columns with queens
diag1 = set() # row - col diagonals
diag2 = set() # row + col anti-diagonals
def backtrack(row: int):
if row == n:
# Found valid placement - convert to board representation
solution = []
for r in range(n):
line = '.' * board[r] + 'Q' + '.' * (n - board[r] - 1)
solution.append(line)
solutions.append(solution)
return
for col in range(n):
# Check all constraints in O(1)
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# Place queen
board[row] = col
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
# Remove queen (backtrack)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return solutions
Sudoku Solver¶
def solve_sudoku(board: list[list[str]]) -> bool:
"""
Solve Sudoku in-place using backtracking with constraint propagation.
Time: O(9^k) where k = empty cells (~20-50 typically)
Space: O(81) for constraint sets
"""
# Initialize constraint sets
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Populate existing numbers
empty_cells = []
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j])
rows[i].add(num)
cols[j].add(num)
boxes[(i // 3) * 3 + j // 3].add(num)
else:
empty_cells.append((i, j))
def backtrack(idx: int) -> bool:
if idx == len(empty_cells):
return True # All cells filled
i, j = empty_cells[idx]
box_idx = (i // 3) * 3 + j // 3
for num in range(1, 10):
if num in rows[i] or num in cols[j] or num in boxes[box_idx]:
continue
# Place number
board[i][j] = str(num)
rows[i].add(num)
cols[j].add(num)
boxes[box_idx].add(num)
if backtrack(idx + 1):
return True
# Backtrack
board[i][j] = '.'
rows[i].remove(num)
cols[j].remove(num)
boxes[box_idx].remove(num)
return False
return backtrack(0)
Graph Coloring¶
Assign colors to vertices such that no adjacent vertices share the same color.
def graph_coloring(graph: dict[int, list[int]], num_colors: int) -> dict[int, int] | None:
"""
Color graph vertices using at most num_colors colors.
graph: adjacency list {vertex: [neighbors]}
Returns: {vertex: color} or None if impossible
Time: O(k^n) worst case where k = colors, n = vertices
Space: O(n) for coloring
"""
vertices = list(graph.keys())
coloring = {}
def is_safe(vertex: int, color: int) -> bool:
return all(coloring.get(neighbor) != color for neighbor in graph[vertex])
def backtrack(idx: int) -> bool:
if idx == len(vertices):
return True
vertex = vertices[idx]
for color in range(num_colors):
if is_safe(vertex, color):
coloring[vertex] = color
if backtrack(idx + 1):
return True
del coloring[vertex]
return False
# Order vertices by degree (most constrained first)
vertices.sort(key=lambda v: len(graph[v]), reverse=True)
return coloring if backtrack(0) else None
Hamiltonian Path¶
Find a path visiting every vertex exactly once.
def hamiltonian_path(graph: dict[int, list[int]]) -> list[int] | None:
"""
Find Hamiltonian path using backtracking.
Time: O(n! * n) worst case
Space: O(n) for path and visited set
"""
n = len(graph)
vertices = list(graph.keys())
def backtrack(path: list[int], visited: set[int]) -> list[int] | None:
if len(path) == n:
return path.copy()
current = path[-1]
for neighbor in graph[current]:
if neighbor not in visited:
path.append(neighbor)
visited.add(neighbor)
result = backtrack(path, visited)
if result:
return result
path.pop()
visited.remove(neighbor)
return None
# Try each vertex as starting point
for start in vertices:
result = backtrack([start], {start})
if result:
return result
return None
Subset Sum / Combination Sum¶
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""
Find all unique combinations that sum to target (can reuse elements).
Time: O(n^(target/min)) where min = smallest candidate
Space: O(target/min) for recursion depth
"""
results = []
candidates.sort() # Enable early termination
def backtrack(start: int, current: list[int], remaining: int):
if remaining == 0:
results.append(current.copy())
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # Pruning: sorted, so all following are larger
current.append(candidates[i])
backtrack(i, current, remaining - candidates[i]) # i not i+1: can reuse
current.pop()
backtrack(0, [], target)
return results
Permutations and Combinations¶
def permutations(nums: list[int]) -> list[list[int]]:
"""
Generate all permutations using backtracking.
Time: O(n! * n), Space: O(n)
"""
result = []
used = [False] * len(nums)
def backtrack(current: list[int]):
if len(current) == len(nums):
result.append(current.copy())
return
for i in range(len(nums)):
if used[i]:
continue
# Skip duplicates (for sorted input with duplicates)
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
current.append(nums[i])
backtrack(current)
current.pop()
used[i] = False
nums.sort() # For duplicate handling
backtrack([])
return result
def combinations(n: int, k: int) -> list[list[int]]:
"""
Generate all k-combinations of 1..n.
Time: O(C(n,k) * k), Space: O(k)
"""
result = []
def backtrack(start: int, current: list[int]):
if len(current) == k:
result.append(current.copy())
return
# Pruning: need k - len(current) more elements
# Can only go up to n - (k - len(current)) + 1
for i in range(start, n - (k - len(current)) + 2):
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
1.6 Advanced Variants¶
- Branch-and-Bound: Add bounds (upper/lower) to prune suboptimal branches (e.g., TSP with MST lower bound).
- Dancing Links (DLX): Knuth's sparse matrix technique for exact cover problems; O(1) per link operation.
- Parallel Backtracking: Work-stealing queues distribute subtrees; span O(d/p) with p processors.
- Hybrid with DP: Memoize partial states (e.g., TSP with bitmask DP achieves O(2^n × n²)).
1.7 Pros/Cons and Practical Considerations¶
| Pros | Cons |
|---|---|
| Exact solutions for finite CSP | Exponential worst-case |
| Intuitive tree-based reasoning | Sensitive to variable/value ordering |
| Flexible constraint handling | Memory for deep recursion |
| Integrates with propagation | May need problem-specific pruning |
Empirical Performance: N-Queens n=20 solves in ~1s; Sudoku hard instances <1s; Graph coloring highly dependent on structure.
2. String Algorithms¶
String algorithms for pattern matching address the fundamental challenge of locating occurrences of a pattern P (length m) within a text T (length n, typically n >> m), optimizing beyond the naive O(nm) quadratic time. These algorithms preprocess P to enable sublinear or linear scans, leveraging preprocessing for skips (KMP, Boyer-Moore) or probabilistic fingerprints (Rabin-Karp). They form the backbone of search engines, bioinformatics, and compilers.
2.1 Knuth-Morris-Pratt (KMP)¶
KMP (1977) preprocesses P to compute a failure (prefix) table π, enabling the matcher to "remember" partial matches and skip redundant comparisons—effectively building a finite automaton.
Core Concepts:
- Prefix Table π:
π[i]= length of longest proper prefix ofP[0..i]that is also a suffix (called "border"). - Matcher State q: Current number of characters matched in P.
- Key Insight: On mismatch, use border information to shift pattern without missing potential matches.
class KMP:
"""
Knuth-Morris-Pratt pattern matching algorithm.
Time Complexity:
- Preprocessing: O(m)
- Search: O(n)
- Total: O(n + m)
Space Complexity: O(m) for failure table
"""
@staticmethod
def build_failure_table(pattern: str) -> list[int]:
"""
Build failure/prefix table for pattern.
pi[i] = length of longest proper prefix of pattern[0..i]
that is also a suffix
"""
m = len(pattern)
pi = [0] * m
k = 0 # Length of previous longest prefix suffix
for i in range(1, m):
# Fall back until we find a match or reach start
while k > 0 and pattern[i] != pattern[k]:
k = pi[k - 1]
if pattern[i] == pattern[k]:
k += 1
pi[i] = k
return pi
@staticmethod
def search(text: str, pattern: str) -> list[int]:
"""Find all occurrences of pattern in text."""
if not pattern:
return list(range(len(text) + 1))
if not text or len(pattern) > len(text):
return []
pi = KMP.build_failure_table(pattern)
matches = []
q = 0 # Number of characters matched
for i in range(len(text)):
# Fall back on mismatch
while q > 0 and text[i] != pattern[q]:
q = pi[q - 1]
if text[i] == pattern[q]:
q += 1
if q == len(pattern):
matches.append(i - len(pattern) + 1)
q = pi[q - 1] # Continue searching for overlapping matches
return matches
Correctness Proof:
- π is maximal: By induction on i, π[i] equals the longest k where P[0..k-1] = P[i-k+1..i].
- No false negatives: Every valid alignment is checked; shifts via borders preserve all potential matches.
- Linear time: Each while iteration decreases q; total decreases ≤ total increases ≤ n + m.
2.2 Boyer-Moore Algorithm¶
Boyer-Moore (1977) is often faster than KMP in practice, especially for large alphabets. It scans the pattern from right to left and uses two heuristics to skip comparisons.
Two Key Heuristics:
-
Bad Character Rule: On mismatch at position j, shift pattern so that:
- The mismatched text character aligns with its rightmost occurrence in pattern, OR
- Pattern moves past the mismatch point if character doesn't exist in pattern
-
Good Suffix Rule: On mismatch, shift pattern to align:
- The matched suffix with another occurrence of that suffix in pattern, OR
- A prefix of pattern that matches a suffix of the matched portion
class BoyerMoore:
"""
Boyer-Moore string matching algorithm.
Time Complexity:
- Preprocessing: O(m + |Σ|) where Σ is alphabet
- Search: O(n/m) best case (sublinear!), O(nm) worst case
- With Galil rule: O(n + m) worst case guaranteed
Space Complexity: O(m + |Σ|)
"""
@staticmethod
def build_bad_char_table(pattern: str) -> dict[str, int]:
"""
Build bad character table.
Maps each character to its rightmost position in pattern.
"""
table = {}
for i, char in enumerate(pattern):
table[char] = i
return table
@staticmethod
def build_good_suffix_table(pattern: str) -> list[int]:
"""
Build good suffix table for pattern.
shift[i] = amount to shift when mismatch occurs at position i-1
"""
m = len(pattern)
shift = [0] * (m + 1)
border = [0] * (m + 1)
# Case 1: Matching suffix appears elsewhere in pattern
i = m
j = m + 1
border[i] = j
while i > 0:
while j <= m and pattern[i - 1] != pattern[j - 1]:
if shift[j] == 0:
shift[j] = j - i
j = border[j]
i -= 1
j -= 1
border[i] = j
# Case 2: Only a prefix of pattern matches suffix of matched portion
j = border[0]
for i in range(m + 1):
if shift[i] == 0:
shift[i] = j
if i == j:
j = border[j]
return shift
@staticmethod
def search(text: str, pattern: str) -> list[int]:
"""Find all occurrences of pattern in text."""
if not pattern:
return list(range(len(text) + 1))
if not text or len(pattern) > len(text):
return []
n, m = len(text), len(pattern)
bad_char = BoyerMoore.build_bad_char_table(pattern)
good_suffix = BoyerMoore.build_good_suffix_table(pattern)
matches = []
s = 0 # Shift of pattern with respect to text
while s <= n - m:
j = m - 1 # Start from end of pattern
# Match from right to left
while j >= 0 and pattern[j] == text[s + j]:
j -= 1
if j < 0:
# Full match found
matches.append(s)
s += good_suffix[0]
else:
# Mismatch: use max of both heuristics
char_shift = j - bad_char.get(text[s + j], -1)
suffix_shift = good_suffix[j + 1]
s += max(char_shift, suffix_shift)
return matches
Comparison: KMP vs Boyer-Moore
| Aspect | KMP | Boyer-Moore |
|---|---|---|
| Scan direction | Left to right | Right to left |
| Best case | O(n) | O(n/m) sublinear |
| Worst case | O(n + m) | O(nm), O(n+m) with Galil |
| Preprocessing | O(m) | O(m + |Σ|) |
| Best for | Small alphabet, streaming | Large alphabet, long patterns |
2.3 Z-Algorithm¶
The Z-algorithm computes the Z-array in O(n) time, where Z[i] = length of longest substring starting at i that matches a prefix of the string.
def z_algorithm(s: str) -> list[int]:
"""
Compute Z-array for string s.
Z[i] = length of longest substring starting at i that matches prefix of s.
Time: O(n), Space: O(n)
Applications:
- Pattern matching: Concatenate P + '$' + T, find Z[i] == len(P)
- String periodicity: Smallest k where Z[k] + k == n
- Longest repeated prefix
"""
n = len(s)
if n == 0:
return []
z = [0] * n
z[0] = n # By definition, entire string matches itself
# [l, r] = Z-box: rightmost interval with Z[l] > 0 that extends furthest
l = r = 0
for i in range(1, n):
if i < r:
# i is within Z-box, use precomputed value
z[i] = min(r - i, z[i - l])
# Extend Z[i] by direct comparison
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
# Update Z-box if extended past r
if i + z[i] > r:
l, r = i, i + z[i]
return z
def z_pattern_match(text: str, pattern: str) -> list[int]:
"""Pattern matching using Z-algorithm. O(n + m) time."""
combined = pattern + '$' + text # '$' not in pattern or text
z = z_algorithm(combined)
m = len(pattern)
return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
2.4 Rabin-Karp: Rolling Hash¶
Rabin-Karp (1987) treats strings as numbers using polynomial hashing, enabling O(1) window slides via rolling hash computation.
class RabinKarp:
"""
Rabin-Karp pattern matching with rolling hash.
Time: O(n + m) average, O(nm) worst (adversarial collisions)
Space: O(1)
Advantages: Simple, generalizes to multiple patterns, 2D matching
Disadvantages: Probabilistic (false positives require verification)
"""
def __init__(self, base: int = 256, mod: int = 10**9 + 7):
self.base = base
self.mod = mod
def search(self, text: str, pattern: str) -> list[int]:
"""Find all occurrences of pattern in text."""
n, m = len(text), len(pattern)
if m > n or m == 0:
return [] if m > n else list(range(n + 1))
# Precompute base^(m-1) mod p
h = pow(self.base, m - 1, self.mod)
# Compute initial hashes
p_hash = 0
t_hash = 0
for i in range(m):
p_hash = (p_hash * self.base + ord(pattern[i])) % self.mod
t_hash = (t_hash * self.base + ord(text[i])) % self.mod
matches = []
for i in range(n - m + 1):
# Check hash match, then verify to avoid false positives
if p_hash == t_hash:
if text[i:i + m] == pattern: # O(m) verification
matches.append(i)
# Roll hash to next window
if i < n - m:
# Remove leading character, add trailing character
t_hash = (t_hash - ord(text[i]) * h) % self.mod
t_hash = (t_hash * self.base + ord(text[i + m])) % self.mod
t_hash = (t_hash + self.mod) % self.mod # Ensure positive
return matches
def multi_pattern_search(self, text: str, patterns: list[str]) -> dict[str, list[int]]:
"""Search for multiple patterns (same length) efficiently."""
if not patterns:
return {}
m = len(patterns[0])
if any(len(p) != m for p in patterns):
raise ValueError("All patterns must have same length")
# Hash all patterns
pattern_hashes = {}
for p in patterns:
h = sum(ord(c) * pow(self.base, m - 1 - i, self.mod)
for i, c in enumerate(p)) % self.mod
pattern_hashes.setdefault(h, []).append(p)
results = {p: [] for p in patterns}
# Single pass over text
n = len(text)
h_power = pow(self.base, m - 1, self.mod)
t_hash = sum(ord(text[i]) * pow(self.base, m - 1 - i, self.mod)
for i in range(min(m, n))) % self.mod
for i in range(n - m + 1):
if t_hash in pattern_hashes:
for p in pattern_hashes[t_hash]:
if text[i:i + m] == p:
results[p].append(i)
if i < n - m:
t_hash = ((t_hash - ord(text[i]) * h_power) * self.base +
ord(text[i + m])) % self.mod
t_hash = (t_hash + self.mod) % self.mod
return results
2.5 Aho-Corasick: Multi-Pattern Matching¶
Aho-Corasick builds a trie with failure links for efficient multi-pattern searching.
from collections import deque, defaultdict
class AhoCorasick:
"""
Aho-Corasick algorithm for multi-pattern matching.
Time: O(n + m + z) where n = text length, m = total pattern length, z = matches
Space: O(m) for trie
Applications: Spam filtering, DNA sequence analysis, intrusion detection
"""
def __init__(self):
self.goto = [{}] # Goto function (trie transitions)
self.fail = [0] # Failure function
self.output = [[]] # Output function (patterns ending at state)
self.state_count = 1
def add_pattern(self, pattern: str, pattern_id: int = None):
"""Add a pattern to the automaton."""
state = 0
for char in pattern:
if char not in self.goto[state]:
self.goto[state][char] = self.state_count
self.goto.append({})
self.fail.append(0)
self.output.append([])
self.state_count += 1
state = self.goto[state][char]
self.output[state].append(pattern_id if pattern_id is not None else pattern)
def build(self):
"""Build failure links using BFS."""
queue = deque()
# Initialize: depth-1 states have fail = 0
for char, state in self.goto[0].items():
queue.append(state)
self.fail[state] = 0
# BFS to compute failure function
while queue:
curr = queue.popleft()
for char, next_state in self.goto[curr].items():
queue.append(next_state)
# Find failure state
failure = self.fail[curr]
while failure and char not in self.goto[failure]:
failure = self.fail[failure]
self.fail[next_state] = self.goto[failure].get(char, 0)
# Merge output sets
self.output[next_state] = (
self.output[next_state] +
self.output[self.fail[next_state]]
)
def search(self, text: str) -> list[tuple[int, any]]:
"""
Search text for all patterns.
Returns: [(position, pattern_id), ...]
"""
results = []
state = 0
for i, char in enumerate(text):
# Follow failure links until match or root
while state and char not in self.goto[state]:
state = self.fail[state]
state = self.goto[state].get(char, 0)
# Report all matches ending at position i
for pattern_id in self.output[state]:
results.append((i, pattern_id))
return results
2.6 Suffix Array¶
A suffix array is a sorted array of all suffixes of a string, enabling efficient pattern matching and substring queries.
def build_suffix_array(s: str) -> list[int]:
"""
Build suffix array using doubling algorithm.
Time: O(n log n), Space: O(n)
"""
n = len(s)
if n == 0:
return []
# Initial ranking based on first character
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0] * n
k = 1 # Current comparison length
while k < n:
# Sort by (rank[i], rank[i+k])
def key(i):
return (rank[i], rank[i + k] if i + k < n else -1)
sa.sort(key=key)
# Compute new ranks
tmp[sa[0]] = 0
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i-1]]
if key(sa[i]) != key(sa[i-1]):
tmp[sa[i]] += 1
rank = tmp.copy()
# Early termination if all ranks unique
if rank[sa[n-1]] == n - 1:
break
k *= 2
return sa
def build_lcp_array(s: str, sa: list[int]) -> list[int]:
"""
Build LCP (Longest Common Prefix) array using Kasai's algorithm.
lcp[i] = length of common prefix between sa[i] and sa[i-1]
Time: O(n), Space: O(n)
"""
n = len(s)
rank = [0] * n
for i, suffix_start in enumerate(sa):
rank[suffix_start] = i
lcp = [0] * n
k = 0 # Current LCP length
for i in range(n):
if rank[i] == 0:
k = 0
continue
j = sa[rank[i] - 1] # Previous suffix in sorted order
while i + k < n and j + k < n and s[i + k] == s[j + k]:
k += 1
lcp[rank[i]] = k
if k > 0:
k -= 1 # Key insight: LCP decreases by at most 1
return lcp
def pattern_match_suffix_array(text: str, pattern: str, sa: list[int]) -> list[int]:
"""
Find all occurrences of pattern using suffix array binary search.
Time: O(m log n) where m = pattern length, n = text length
"""
n, m = len(text), len(pattern)
# Binary search for leftmost match
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
suffix = text[sa[mid]:sa[mid] + m]
if suffix < pattern:
lo = mid + 1
else:
hi = mid
left = lo
# Binary search for rightmost match
hi = n
while lo < hi:
mid = (lo + hi) // 2
suffix = text[sa[mid]:sa[mid] + m]
if suffix <= pattern:
lo = mid + 1
else:
hi = mid
right = lo
return [sa[i] for i in range(left, right)]
2.7 Manacher's Algorithm: All Palindromes in O(n)¶
def manacher(s: str) -> tuple[str, int, int]:
"""
Find longest palindromic substring using Manacher's algorithm.
Time: O(n), Space: O(n)
Returns: (longest_palindrome, start_index, length)
"""
if not s:
return "", 0, 0
# Transform: "abc" -> "^#a#b#c#$" to handle even-length palindromes
t = '^#' + '#'.join(s) + '#$'
n = len(t)
p = [0] * n # p[i] = radius of palindrome centered at i
center = right = 0 # Center and right boundary of rightmost palindrome
for i in range(1, n - 1):
if i < right:
# Use mirror property
mirror = 2 * center - i
p[i] = min(right - i, p[mirror])
# Expand around center i
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# Update center if expanded past right
if i + p[i] > right:
center, right = i, i + p[i]
# Find maximum
max_len = max(p)
center_idx = p.index(max_len)
# Convert back to original indices
start = (center_idx - max_len) // 2
return s[start:start + max_len], start, max_len
2.8 Algorithm Selection Guide¶
| Problem | Best Algorithm | Time | When to Use |
|---|---|---|---|
| Single pattern, any alphabet | KMP | O(n + m) | General purpose, streaming |
| Single pattern, large alphabet | Boyer-Moore | O(n/m) avg | English text, DNA |
| Multiple same-length patterns | Rabin-Karp | O(n + km) | Plagiarism detection |
| Multiple different patterns | Aho-Corasick | O(n + Σm + z) | Virus scanning, filtering |
| Many substring queries | Suffix Array | O(m log n) per query | After O(n log n) build |
| Longest palindrome | Manacher | O(n) | String analysis |
3. Divide-and-Conquer¶
Divide-and-Conquer (D&C) is a recursive paradigm that solves problems by: 1. Dividing into smaller, independent subproblems 2. Conquering subproblems recursively 3. Combining results to form the final solution
The Master Theorem characterizes D&C complexity: T(n) = a·T(n/b) + f(n), where a ≥ 1 subproblems of size n/b with f(n) combine cost.
3.1 Closest Pair of Points¶
Find the minimum Euclidean distance between any two points in a plane, reducing O(n²) brute force to O(n log n).
import math
from typing import NamedTuple
class Point(NamedTuple):
x: float
y: float
def closest_pair(points: list[Point]) -> tuple[float, Point, Point]:
"""
Find closest pair of points in 2D plane.
Time: O(n log n) - presort + recursion with linear merge
Space: O(n) for sorted copies
Returns: (distance, point1, point2)
"""
def distance(p1: Point, p2: Point) -> float:
return math.sqrt((p1.x - p2.x)**2 + (p1.y - p2.y)**2)
def brute_force(pts: list[Point]) -> tuple[float, Point, Point]:
min_dist = float('inf')
pair = (pts[0], pts[1]) if len(pts) >= 2 else (None, None)
for i in range(len(pts)):
for j in range(i + 1, len(pts)):
d = distance(pts[i], pts[j])
if d < min_dist:
min_dist = d
pair = (pts[i], pts[j])
return min_dist, pair[0], pair[1]
def closest_util(px: list[Point], py: list[Point]) -> tuple[float, Point, Point]:
n = len(px)
# Base case: brute force for small inputs
if n <= 3:
return brute_force(px)
# Divide: split by x-coordinate
mid = n // 2
mid_point = px[mid]
# Split py into left and right maintaining y-sort
pyl = [p for p in py if p.x <= mid_point.x]
pyr = [p for p in py if p.x > mid_point.x]
# Handle edge case where all points have same x
if not pyr:
pyl = py[:mid]
pyr = py[mid:]
# Conquer: recurse on halves
dl, p1l, p2l = closest_util(px[:mid], pyl)
dr, p1r, p2r = closest_util(px[mid:], pyr)
if dl < dr:
delta, p1, p2 = dl, p1l, p2l
else:
delta, p1, p2 = dr, p1r, p2r
# Combine: check strip of width 2*delta around midline
strip = [p for p in py if abs(p.x - mid_point.x) < delta]
# Key insight: only need to check 7 points ahead in y-sorted strip
# Proof: In δ×2δ box, at most 8 points (pigeonhole with δ/2 grid)
for i in range(len(strip)):
for j in range(i + 1, min(i + 8, len(strip))):
if strip[j].y - strip[i].y >= delta:
break # Further points are too far in y
d = distance(strip[i], strip[j])
if d < delta:
delta, p1, p2 = d, strip[i], strip[j]
return delta, p1, p2
# Presort by x and y coordinates
px = sorted(points, key=lambda p: p.x)
py = sorted(points, key=lambda p: p.y)
return closest_util(px, py)
3.2 Karatsuba Multiplication¶
Multiply two n-digit numbers in O(n^1.585) instead of O(n²).
def karatsuba(x: int, y: int) -> int:
"""
Karatsuba multiplication algorithm.
Time: T(n) = 3T(n/2) + O(n) = O(n^log₂3) ≈ O(n^1.585)
Space: O(n) for recursion
Key insight: (a*10^m + b)(c*10^m + d) = ac*10^2m + ((a+b)(c+d) - ac - bd)*10^m + bd
Only 3 multiplications instead of 4!
"""
# Base case
if x < 10 or y < 10:
return x * y
# Calculate size
n = max(len(str(abs(x))), len(str(abs(y))))
m = n // 2
# Split numbers: x = a * 10^m + b, y = c * 10^m + d
power = 10 ** m
a, b = divmod(x, power)
c, d = divmod(y, power)
# Three recursive multiplications
ac = karatsuba(a, c)
bd = karatsuba(b, d)
ad_bc = karatsuba(a + b, c + d) - ac - bd # (a+b)(c+d) - ac - bd = ad + bc
# Combine: ac * 10^2m + (ad + bc) * 10^m + bd
return ac * (10 ** (2 * m)) + ad_bc * (10 ** m) + bd
3.3 Strassen's Matrix Multiplication¶
Multiply two n×n matrices in O(n^2.807) instead of O(n³).
import numpy as np
def strassen(A: np.ndarray, B: np.ndarray) -> np.ndarray:
"""
Strassen's matrix multiplication algorithm.
Time: T(n) = 7T(n/2) + O(n²) = O(n^log₂7) ≈ O(n^2.807)
Space: O(n² log n) for recursive matrices
Key insight: 7 multiplications instead of 8 using clever linear combinations
Practical: Crossover to naive at n ≈ 32-128 due to cache effects
"""
n = A.shape[0]
# Base case: use naive multiplication for small matrices
if n <= 64:
return A @ B
# Ensure dimensions are powers of 2 (pad if necessary)
if n % 2 != 0:
A = np.pad(A, ((0, 1), (0, 1)))
B = np.pad(B, ((0, 1), (0, 1)))
result = strassen(A, B)
return result[:n, :n]
# Split into quadrants
mid = n // 2
A11, A12 = A[:mid, :mid], A[:mid, mid:]
A21, A22 = A[mid:, :mid], A[mid:, mid:]
B11, B12 = B[:mid, :mid], B[:mid, mid:]
B21, B22 = B[mid:, :mid], B[mid:, mid:]
# Strassen's 7 products
M1 = strassen(A11 + A22, B11 + B22)
M2 = strassen(A21 + A22, B11)
M3 = strassen(A11, B12 - B22)
M4 = strassen(A22, B21 - B11)
M5 = strassen(A11 + A12, B22)
M6 = strassen(A21 - A11, B11 + B12)
M7 = strassen(A12 - A22, B21 + B22)
# Combine results
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
# Assemble result
C = np.zeros((n, n))
C[:mid, :mid] = C11
C[:mid, mid:] = C12
C[mid:, :mid] = C21
C[mid:, mid:] = C22
return C
3.4 Fast Fourier Transform (FFT)¶
Multiply polynomials in O(n log n) using the convolution theorem.
import cmath
def fft(a: list[complex], invert: bool = False) -> list[complex]:
"""
Cooley-Tukey FFT algorithm.
Time: O(n log n), Space: O(n)
Computes DFT: X[k] = Σ x[n] * e^(-2πi*kn/N)
Or inverse: x[n] = (1/N) * Σ X[k] * e^(2πi*kn/N)
"""
n = len(a)
if n == 1:
return a
# Ensure n is power of 2
if n & (n - 1) != 0:
# Pad to next power of 2
next_pow2 = 1 << (n - 1).bit_length()
a = a + [0] * (next_pow2 - n)
n = next_pow2
# Bit-reversal permutation
result = a.copy()
j = 0
for i in range(1, n):
bit = n >> 1
while j & bit:
j ^= bit
bit >>= 1
j ^= bit
if i < j:
result[i], result[j] = result[j], result[i]
# Cooley-Tukey iterative FFT
length = 2
while length <= n:
angle = 2 * cmath.pi / length * (-1 if invert else 1)
wlen = cmath.exp(1j * angle)
for i in range(0, n, length):
w = 1
for j in range(length // 2):
u = result[i + j]
v = result[i + j + length // 2] * w
result[i + j] = u + v
result[i + j + length // 2] = u - v
w *= wlen
length *= 2
if invert:
result = [x / n for x in result]
return result
def multiply_polynomials(a: list[int], b: list[int]) -> list[int]:
"""
Multiply two polynomials using FFT convolution.
Time: O(n log n) instead of O(n²) naive
a, b: Coefficient lists where a[i] = coefficient of x^i
Returns: Coefficients of product polynomial
"""
# Result degree is len(a) + len(b) - 2, need len(a) + len(b) - 1 coefficients
result_len = len(a) + len(b) - 1
n = 1
while n < result_len:
n *= 2
# Pad to length n
fa = [complex(x) for x in a] + [0] * (n - len(a))
fb = [complex(x) for x in b] + [0] * (n - len(b))
# FFT both
fa = fft(fa)
fb = fft(fb)
# Point-wise multiplication
fc = [fa[i] * fb[i] for i in range(n)]
# Inverse FFT
fc = fft(fc, invert=True)
# Round to integers
return [round(x.real) for x in fc[:result_len]]
3.5 Maximum Subarray (D&C approach)¶
def max_crossing_sum(arr: list[int], low: int, mid: int, high: int) -> tuple[int, int, int]:
"""Find max subarray that crosses the midpoint."""
# Left half: must include arr[mid]
left_sum = float('-inf')
curr_sum = 0
left_idx = mid
for i in range(mid, low - 1, -1):
curr_sum += arr[i]
if curr_sum > left_sum:
left_sum = curr_sum
left_idx = i
# Right half: must include arr[mid + 1]
right_sum = float('-inf')
curr_sum = 0
right_idx = mid + 1
for i in range(mid + 1, high + 1):
curr_sum += arr[i]
if curr_sum > right_sum:
right_sum = curr_sum
right_idx = i
return left_sum + right_sum, left_idx, right_idx
def max_subarray_dc(arr: list[int]) -> tuple[int, int, int]:
"""
Find maximum subarray using divide and conquer.
Time: T(n) = 2T(n/2) + O(n) = O(n log n)
Space: O(log n) recursion
Note: Kadane's algorithm is O(n) but this demonstrates D&C pattern
Returns: (max_sum, start_index, end_index)
"""
def helper(low: int, high: int) -> tuple[int, int, int]:
if low == high:
return arr[low], low, low
mid = (low + high) // 2
# Maximum in left half
left_sum, left_low, left_high = helper(low, mid)
# Maximum in right half
right_sum, right_low, right_high = helper(mid + 1, high)
# Maximum crossing midpoint
cross_sum, cross_low, cross_high = max_crossing_sum(arr, low, mid, high)
# Return maximum of three
if left_sum >= right_sum and left_sum >= cross_sum:
return left_sum, left_low, left_high
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_sum, right_low, right_high
else:
return cross_sum, cross_low, cross_high
return helper(0, len(arr) - 1)
3.6 Merge Sort (Inversion Count)¶
def count_inversions(arr: list[int]) -> tuple[list[int], int]:
"""
Count inversions (i < j but arr[i] > arr[j]) using merge sort.
Time: O(n log n), Space: O(n)
Applications: Measure "sortedness", collaborative filtering similarity
"""
def merge_count(arr: list[int]) -> tuple[list[int], int]:
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_count(arr[:mid])
right, right_inv = merge_count(arr[mid:])
# Merge and count split inversions
merged = []
split_inv = 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
# All remaining elements in left are greater than right[j]
split_inv += len(left) - i
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, left_inv + right_inv + split_inv
return merge_count(arr)
3.7 Master Theorem Reference¶
For recurrences of the form T(n) = aT(n/b) + f(n):
| Case | Condition | Time Complexity |
|---|---|---|
| 1 | f(n) = O(n^(log_b(a) - ε)) | T(n) = Θ(n^log_b(a)) |
| 2 | f(n) = Θ(n^log_b(a) log^k n) | T(n) = Θ(n^log_b(a) log^(k+1) n) |
| 3 | f(n) = Ω(n^(log_b(a) + ε)) and regularity | T(n) = Θ(f(n)) |
| Algorithm | Recurrence | Result |
|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Karatsuba | T(n) = 3T(n/2) + O(n) | O(n^1.585) |
| Strassen | T(n) = 7T(n/2) + O(n²) | O(n^2.807) |
| Closest Pair | T(n) = 2T(n/2) + O(n) | O(n log n) |
4. Bit Manipulation¶
Bit manipulation techniques leverage the binary representation of integers for efficient computation. These operations run in O(1) time on fixed-width integers and are fundamental in systems programming, cryptography, and competitive programming.
4.1 Fundamental Operations¶
# Basic bit operations
def get_bit(n: int, i: int) -> int:
"""Get i-th bit (0-indexed from right)."""
return (n >> i) & 1
def set_bit(n: int, i: int) -> int:
"""Set i-th bit to 1."""
return n | (1 << i)
def clear_bit(n: int, i: int) -> int:
"""Clear i-th bit to 0."""
return n & ~(1 << i)
def toggle_bit(n: int, i: int) -> int:
"""Toggle i-th bit."""
return n ^ (1 << i)
def update_bit(n: int, i: int, v: int) -> int:
"""Update i-th bit to value v (0 or 1)."""
mask = ~(1 << i)
return (n & mask) | (v << i)
4.2 Common Techniques and Tricks¶
# Check if power of 2
def is_power_of_two(n: int) -> bool:
"""n is power of 2 iff it has exactly one set bit."""
return n > 0 and (n & (n - 1)) == 0
# Count set bits (Brian Kernighan's algorithm)
def count_bits(n: int) -> int:
"""
Count number of 1s in binary representation.
Time: O(number of set bits)
"""
count = 0
while n:
n &= (n - 1) # Clear lowest set bit
count += 1
return count
# Alternatively, use lookup table for O(1)
def count_bits_lookup(n: int, table: list[int] = None) -> int:
"""O(1) using 8-bit lookup table."""
if table is None:
table = [bin(i).count('1') for i in range(256)]
count = 0
while n:
count += table[n & 0xFF]
n >>= 8
return count
# Lowest set bit (isolate)
def lowest_set_bit(n: int) -> int:
"""Get value of lowest set bit. Uses two's complement."""
return n & (-n)
# Highest set bit position
def highest_bit_position(n: int) -> int:
"""Position of highest set bit (0-indexed)."""
if n <= 0:
return -1
pos = 0
while n > 1:
n >>= 1
pos += 1
return pos
# Or using bit_length()
def highest_bit_position_fast(n: int) -> int:
return n.bit_length() - 1 if n > 0 else -1
# Check if bits alternate (like 101010...)
def has_alternating_bits(n: int) -> bool:
"""Check if adjacent bits are different."""
xor = n ^ (n >> 1)
return (xor & (xor + 1)) == 0
# Swap two numbers without temp variable
def swap_xor(a: int, b: int) -> tuple[int, int]:
"""XOR swap: a^b^b = a, a^b^a = b."""
if a != b: # Important: fails if a and b refer to same memory
a ^= b
b ^= a
a ^= b
return a, b
4.3 Classic Problems¶
# Single Number: Find element appearing once (others appear twice)
def single_number(nums: list[int]) -> int:
"""
XOR all elements: a^a = 0, so duplicates cancel out.
Time: O(n), Space: O(1)
"""
result = 0
for num in nums:
result ^= num
return result
# Single Number II: Find element appearing once (others appear three times)
def single_number_three_times(nums: list[int]) -> int:
"""
Track bits that appear 1, 2 times; reset at 3.
Time: O(n), Space: O(1)
"""
ones = twos = 0
for num in nums:
# ones holds bits appearing once (mod 3)
# twos holds bits appearing twice (mod 3)
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
return ones
# Missing Number: Find missing number in [0, n]
def missing_number(nums: list[int]) -> int:
"""
XOR with indices: pairs cancel, leaves missing.
Time: O(n), Space: O(1)
"""
result = len(nums)
for i, num in enumerate(nums):
result ^= i ^ num
return result
# Reverse Bits
def reverse_bits(n: int) -> int:
"""Reverse 32-bit unsigned integer."""
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result
# Number of 1 Bits (Hamming Weight)
def hamming_weight(n: int) -> int:
"""Count set bits using Brian Kernighan."""
count = 0
while n:
n &= n - 1
count += 1
return count
# Hamming Distance between two integers
def hamming_distance(x: int, y: int) -> int:
"""Number of positions where bits differ."""
return hamming_weight(x ^ y)
# Power of Four
def is_power_of_four(n: int) -> bool:
"""
Power of 4: single bit at even position (0, 2, 4, ...).
0x55555555 = 01010101... in binary
"""
return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0
4.4 Bitmask Dynamic Programming¶
Bitmasks represent subsets of n elements using n bits, enabling DP over all subsets.
# Traveling Salesman Problem with bitmask DP
def tsp_bitmask(dist: list[list[int]]) -> int:
"""
Find minimum cost Hamiltonian cycle using bitmask DP.
State: dp[mask][i] = min cost to visit cities in mask, ending at i
Time: O(2^n * n²), Space: O(2^n * n)
"""
n = len(dist)
INF = float('inf')
# dp[mask][i] = min cost to reach state (mask, i)
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # Start at city 0
for mask in range(1 << n):
for last in range(n):
if dp[mask][last] == INF:
continue
if not (mask & (1 << last)):
continue
# Try visiting unvisited city
for next_city in range(n):
if mask & (1 << next_city):
continue # Already visited
new_mask = mask | (1 << next_city)
new_cost = dp[mask][last] + dist[last][next_city]
dp[new_mask][next_city] = min(dp[new_mask][next_city], new_cost)
# Return to start
full_mask = (1 << n) - 1
return min(dp[full_mask][i] + dist[i][0] for i in range(n))
# Subset Sum using bitmask
def subset_sums(nums: list[int]) -> list[int]:
"""
Generate all possible subset sums.
Time: O(2^n), Space: O(2^n)
"""
n = len(nums)
sums = []
for mask in range(1 << n):
total = sum(nums[i] for i in range(n) if mask & (1 << i))
sums.append(total)
return sums
# Iterate over all subsets of a mask
def iterate_subsets(mask: int):
"""
Iterate over all subsets of mask (including empty and mask itself).
Key trick: submask = (submask - 1) & mask
Time: O(2^popcount(mask))
"""
submask = mask
while submask:
yield submask
submask = (submask - 1) & mask
yield 0 # Empty subset
4.5 Bit Manipulation Reference¶
| Operation | Expression | Result |
|---|---|---|
| Set bit i | n \| (1 << i) |
Bit i becomes 1 |
| Clear bit i | n & ~(1 << i) |
Bit i becomes 0 |
| Toggle bit i | n ^ (1 << i) |
Bit i flips |
| Check bit i | (n >> i) & 1 |
0 or 1 |
| Clear lowest 1 | n & (n - 1) |
Lowest 1 → 0 |
| Isolate lowest 1 | n & (-n) |
Only lowest 1 |
| Set all bits 0..i | (1 << (i+1)) - 1 |
Mask of i+1 ones |
| Is power of 2 | n & (n - 1) == 0 |
True if single bit |
5. Two Pointers and Sliding Window¶
Two pointers and sliding window are techniques for processing sequences efficiently by maintaining a window or pair of indices.
5.1 Two Pointers Pattern¶
Two pointers move through data, typically inward from both ends or in the same direction, reducing O(n²) to O(n).
# Two Sum (sorted array)
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]:
"""
Find two numbers that sum to target in sorted array.
Time: O(n), Space: O(1)
"""
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return left, right
elif current_sum < target:
left += 1
else:
right -= 1
return -1, -1 # Not found
# Three Sum
def three_sum(nums: list[int]) -> list[list[int]]:
"""
Find all unique triplets that sum to zero.
Time: O(n²), Space: O(1) excluding output
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for first element
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates
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 total < 0:
left += 1
else:
right -= 1
return result
# Container With Most Water
def max_area(height: list[int]) -> int:
"""
Find two lines that form container with maximum water.
Time: O(n), Space: O(1)
Insight: Moving the shorter line might increase area,
moving the taller line can only decrease area.
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
# Remove Duplicates from Sorted Array (in-place)
def remove_duplicates(nums: list[int]) -> int:
"""
Remove duplicates in-place, return new length.
Time: O(n), Space: O(1)
"""
if not nums:
return 0
write = 1 # Position to write next unique element
for read in range(1, len(nums)):
if nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
return write
5.2 Sliding Window Pattern¶
Sliding window maintains a contiguous subarray/substring, useful for finding optimal windows satisfying conditions.
# Fixed-size window: Maximum sum of k consecutive elements
def max_sum_k_consecutive(nums: list[int], k: int) -> int:
"""
Find maximum sum of k consecutive elements.
Time: O(n), Space: O(1)
"""
if len(nums) < k:
return 0
# Initial window
window_sum = sum(nums[:k])
max_sum = window_sum
# Slide window
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 window: Minimum size subarray with sum >= target
def min_subarray_len(target: int, nums: list[int]) -> int:
"""
Find minimum length subarray with sum >= target.
Time: O(n), Space: O(1)
"""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
# Shrink window while sum is sufficient
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
# Longest Substring Without Repeating Characters
def length_of_longest_substring(s: str) -> int:
"""
Find length of longest substring without repeating characters.
Time: O(n), Space: O(min(n, |Σ|))
"""
char_index = {} # Last seen index of each character
max_len = 0
left = 0
for right, char in enumerate(s):
# If char seen and within current window, move left
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# Minimum Window Substring
def min_window(s: str, t: str) -> str:
"""
Find minimum window in s containing all characters of t.
Time: O(|s| + |t|), Space: O(|Σ|)
"""
from collections import Counter
if not s or not t:
return ""
# Count required characters
required = Counter(t)
required_count = len(required)
# Window state
window_counts = {}
formed = 0 # Number of unique chars with required frequency
# Result tracking
min_len = float('inf')
result = (0, 0)
left = 0
for right, char in enumerate(s):
# Expand window
window_counts[char] = window_counts.get(char, 0) + 1
if char in required and window_counts[char] == required[char]:
formed += 1
# Contract window while valid
while formed == required_count:
# Update result
if right - left + 1 < min_len:
min_len = right - left + 1
result = (left, right + 1)
# Remove left character
left_char = s[left]
window_counts[left_char] -= 1
if left_char in required and window_counts[left_char] < required[left_char]:
formed -= 1
left += 1
return s[result[0]:result[1]] if min_len != float('inf') else ""
# Longest Repeating Character Replacement
def character_replacement(s: str, k: int) -> int:
"""
Find longest substring with same characters after at most k replacements.
Time: O(n), Space: O(26) = O(1)
"""
count = {}
max_count = 0 # Max frequency of any character in window
max_len = 0
left = 0
for right, char in enumerate(s):
count[char] = count.get(char, 0) + 1
max_count = max(max_count, count[char])
# Window is valid if: (window_size - max_count) <= k
window_size = right - left + 1
if window_size - max_count > k:
# Shrink window
count[s[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
5.3 Pattern Selection Guide¶
| Problem Pattern | Technique | Key Insight |
|---|---|---|
| Sorted array, find pair | Two pointers from ends | Sum too small → move left; too large → move right |
| Find triplet/quadruplet | Fix one + two pointers | Reduce to two-sum problem |
| Subarray with property | Sliding window | Expand until valid, shrink to optimize |
| Substring problems | Sliding window + hashmap | Track character frequencies |
| Linked list cycle | Fast/slow pointers | Fast catches slow in cycle |
| Palindrome check | Two pointers from ends | Compare characters moving inward |
6. Union-Find (Disjoint Set Union)¶
Union-Find (DSU) maintains a collection of disjoint sets, supporting efficient union and find operations with near-constant amortized time.
6.1 Core Implementation¶
class UnionFind:
"""
Union-Find with path compression and union by rank.
Time: O(α(n)) amortized per operation where α = inverse Ackermann
For practical n, α(n) ≤ 4, effectively O(1)
Space: O(n)
Applications: Kruskal's MST, dynamic connectivity, cycle detection
"""
def __init__(self, n: int):
self.parent = list(range(n)) # parent[i] = parent of i
self.rank = [0] * n # Approximate depth of subtree
self.count = n # Number of disjoint sets
def find(self, x: int) -> int:
"""
Find representative of set containing x with path compression.
Path compression: Make every node on path point directly to root.
"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Recursively compress
return self.parent[x]
def union(self, x: int, y: int) -> bool:
"""
Merge sets containing x and y using union by rank.
Union by rank: Attach smaller tree under root of larger tree.
Returns True if merge happened, False if already in same set.
"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in same set
# Union by rank: attach smaller tree to larger
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1
return True
def connected(self, x: int, y: int) -> bool:
"""Check if x and y are in the same set."""
return self.find(x) == self.find(y)
def get_count(self) -> int:
"""Return number of disjoint sets."""
return self.count
6.2 Union-Find with Size (Alternative)¶
class UnionFindBySize:
"""
Union-Find with union by size instead of rank.
Useful when you need to track component sizes.
"""
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n # Size of each component
def find(self, x: int) -> int:
root = x
while self.parent[root] != root:
root = self.parent[root]
# Path compression (iterative)
while self.parent[x] != root:
next_x = self.parent[x]
self.parent[x] = root
x = next_x
return root
def union(self, x: int, y: int) -> bool:
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# Union by size: attach smaller to larger
if self.size[root_x] < self.size[root_y]:
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
else:
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
return True
def get_size(self, x: int) -> int:
"""Return size of component containing x."""
return self.size[self.find(x)]
6.3 Applications¶
# Number of Connected Components
def count_components(n: int, edges: list[tuple[int, int]]) -> int:
"""Count connected components in undirected graph."""
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.get_count()
# Detect Cycle in Undirected Graph
def has_cycle(n: int, edges: list[tuple[int, int]]) -> bool:
"""Detect if undirected graph has a cycle."""
uf = UnionFind(n)
for u, v in edges:
if uf.connected(u, v):
return True # Edge connects nodes already in same component
uf.union(u, v)
return False
# Kruskal's MST
def kruskal_mst(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
"""
Find Minimum Spanning Tree using Kruskal's algorithm.
edges: [(u, v, weight), ...]
Time: O(E log E) for sorting + O(E α(V)) for union-find
"""
uf = UnionFind(n)
mst = []
# Sort edges by weight
edges.sort(key=lambda e: e[2])
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
if len(mst) == n - 1:
break # MST complete
return mst
# Accounts Merge
def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
"""
Merge accounts with common emails.
accounts[i] = [name, email1, email2, ...]
"""
from collections import defaultdict
email_to_id = {}
email_to_name = {}
# Assign ID to each email
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = len(email_to_id)
email_to_name[email] = name
# Union-Find over emails
uf = UnionFind(len(email_to_id))
for account in accounts:
first_id = email_to_id[account[1]]
for email in account[2:]:
uf.union(first_id, email_to_id[email])
# Group emails by component
components = defaultdict(list)
for email, id in email_to_id.items():
root = uf.find(id)
components[root].append(email)
# Build result
return [[email_to_name[emails[0]]] + sorted(emails)
for emails in components.values()]
# Number of Islands (Union-Find approach)
def num_islands_uf(grid: list[list[str]]) -> int:
"""
Count islands using Union-Find.
Time: O(mn * α(mn)), Space: O(mn)
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
def index(r, c):
return r * cols + c
uf = UnionFind(rows * cols)
water_count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '0':
water_count += 1
else:
# Union with adjacent land cells
for dr, dc in [(0, 1), (1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
uf.union(index(r, c), index(nr, nc))
return uf.get_count() - water_count
6.4 Complexity Analysis¶
| Operation | Naive | Path Compression Only | Union by Rank Only | Both |
|---|---|---|---|---|
| Find | O(n) | O(log n) amortized | O(log n) | O(α(n)) |
| Union | O(n) | O(log n) amortized | O(log n) | O(α(n)) |
| m operations | O(mn) | O(m log n) | O(m log n) | O(m α(n)) |
Where α(n) is the inverse Ackermann function, which grows extremely slowly: - α(n) ≤ 4 for any practical n (even 10^80, the estimated atoms in universe)
7. Randomized Algorithms¶
Randomized algorithms use random choices to achieve efficiency or simplicity, often outperforming deterministic alternatives in practice.
7.1 Classification¶
| Type | Correctness | Time | Example |
|---|---|---|---|
| Las Vegas | Always correct | Expected bound | Randomized QuickSort |
| Monte Carlo | Probabilistically correct | Deterministic bound | Miller-Rabin primality |
7.2 Randomized QuickSelect¶
import random
def quickselect(arr: list[int], k: int) -> int:
"""
Find k-th smallest element using randomized selection.
Time: O(n) expected, O(n²) worst case
Space: O(1) iterative version
Las Vegas: Always correct, random time
"""
def partition(left: int, right: int, pivot_idx: int) -> int:
pivot = arr[pivot_idx]
# Move pivot to end
arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]
store_idx = left
for i in range(left, right):
if arr[i] < pivot:
arr[store_idx], arr[i] = arr[i], arr[store_idx]
store_idx += 1
# Move pivot to final position
arr[store_idx], arr[right] = arr[right], arr[store_idx]
return store_idx
left, right = 0, len(arr) - 1
while True:
if left == right:
return arr[left]
# Random pivot
pivot_idx = random.randint(left, right)
pivot_idx = partition(left, right, pivot_idx)
if k == pivot_idx:
return arr[k]
elif k < pivot_idx:
right = pivot_idx - 1
else:
left = pivot_idx + 1
7.3 Reservoir Sampling¶
def reservoir_sample(stream, k: int) -> list:
"""
Sample k items uniformly at random from a stream of unknown size.
Time: O(n), Space: O(k)
Proof: After seeing n items, each has probability k/n of being in reservoir.
"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
# Replace element with probability k/(i+1)
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
def weighted_reservoir_sample(stream, k: int) -> list:
"""
Weighted reservoir sampling (A-Res algorithm).
stream yields (item, weight) tuples.
"""
import heapq
reservoir = [] # Min-heap of (key, item)
for item, weight in stream:
if weight <= 0:
continue
# Key = u^(1/weight) where u ~ Uniform(0,1)
key = random.random() ** (1.0 / weight)
if len(reservoir) < k:
heapq.heappush(reservoir, (key, item))
elif key > reservoir[0][0]:
heapq.heapreplace(reservoir, (key, item))
return [item for _, item in reservoir]
7.4 Bloom Filter¶
import hashlib
class BloomFilter:
"""
Probabilistic set membership data structure.
No false negatives: If contains() returns False, element definitely not in set.
Possible false positives: If contains() returns True, element probably in set.
False positive rate: (1 - e^(-kn/m))^k
where k = hash functions, n = elements, m = bits
Space: O(m) bits, much smaller than storing actual elements
Time: O(k) per operation
"""
def __init__(self, size: int, num_hashes: int):
self.size = size
self.num_hashes = num_hashes
self.bit_array = [False] * size
def _hashes(self, item: str) -> list[int]:
"""Generate k hash values for item."""
hashes = []
for i in range(self.num_hashes):
# Use different seeds for each hash
h = hashlib.sha256(f"{item}{i}".encode()).hexdigest()
hashes.append(int(h, 16) % self.size)
return hashes
def add(self, item: str):
"""Add item to filter."""
for h in self._hashes(item):
self.bit_array[h] = True
def contains(self, item: str) -> bool:
"""Check if item might be in filter."""
return all(self.bit_array[h] for h in self._hashes(item))
@staticmethod
def optimal_size(n: int, fp_rate: float) -> int:
"""Calculate optimal bit array size for n items and desired false positive rate."""
import math
m = -n * math.log(fp_rate) / (math.log(2) ** 2)
return int(m)
@staticmethod
def optimal_hashes(m: int, n: int) -> int:
"""Calculate optimal number of hash functions."""
import math
k = (m / n) * math.log(2)
return max(1, int(k))
7.5 Skip List¶
import random
class SkipListNode:
def __init__(self, val: int, level: int):
self.val = val
self.forward = [None] * (level + 1)
class SkipList:
"""
Probabilistic alternative to balanced BST.
Time: O(log n) expected for search, insert, delete
Space: O(n) expected
Advantages: Simpler than red-black trees, easy to implement
"""
MAX_LEVEL = 16
P = 0.5 # Probability for level increase
def __init__(self):
self.head = SkipListNode(-1, self.MAX_LEVEL)
self.level = 0
def _random_level(self) -> int:
"""Generate random level with geometric distribution."""
lvl = 0
while random.random() < self.P and lvl < self.MAX_LEVEL:
lvl += 1
return lvl
def search(self, target: int) -> bool:
"""Search for target value."""
current = self.head
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].val < target:
current = current.forward[i]
current = current.forward[0]
return current is not None and current.val == target
def insert(self, num: int):
"""Insert value into skip list."""
update = [None] * (self.MAX_LEVEL + 1)
current = self.head
# Find position at each level
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].val < num:
current = current.forward[i]
update[i] = current
# Generate random level for new node
lvl = self._random_level()
if lvl > self.level:
for i in range(self.level + 1, lvl + 1):
update[i] = self.head
self.level = lvl
# Create and insert new node
new_node = SkipListNode(num, lvl)
for i in range(lvl + 1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def erase(self, num: int) -> bool:
"""Remove value from skip list. Returns True if found and removed."""
update = [None] * (self.MAX_LEVEL + 1)
current = self.head
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].val < num:
current = current.forward[i]
update[i] = current
current = current.forward[0]
if current is None or current.val != num:
return False
# Remove node from each level
for i in range(self.level + 1):
if update[i].forward[i] != current:
break
update[i].forward[i] = current.forward[i]
# Update list level
while self.level > 0 and self.head.forward[self.level] is None:
self.level -= 1
return True
7.6 Miller-Rabin Primality Test¶
def miller_rabin(n: int, k: int = 10) -> bool:
"""
Miller-Rabin primality test.
Monte Carlo: Correct if returns False (composite),
probability ≤ 4^(-k) of error if returns True (probably prime).
Time: O(k log³ n) using fast exponentiation
"""
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# Write n-1 as 2^r * d where d is odd
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Witness loop
def is_composite(a: int) -> bool:
x = pow(a, d, n)
if x == 1 or x == n - 1:
return False
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
return False
return True
# Test k random witnesses
for _ in range(k):
a = random.randrange(2, n - 1)
if is_composite(a):
return False
return True # Probably prime
7.7 Algorithm Classification Summary¶
| Algorithm | Type | Time | Space | Use Case |
|---|---|---|---|---|
| QuickSelect | Las Vegas | O(n) expected | O(1) | k-th element |
| Reservoir Sampling | Las Vegas | O(n) | O(k) | Stream sampling |
| Bloom Filter | Monte Carlo | O(k) | O(m) bits | Set membership |
| Skip List | Las Vegas | O(log n) expected | O(n) | Ordered set |
| Miller-Rabin | Monte Carlo | O(k log³ n) | O(1) | Primality |
| Karger Min-Cut | Monte Carlo | O(n²) | O(n²) | Graph min-cut |
8. Summary: Algorithm Selection Guide¶
Pattern Recognition¶
| Problem Characteristics | Recommended Paradigm |
|---|---|
| Enumerate all solutions with constraints | Backtracking |
| Find pattern in text | String algorithms (KMP/Boyer-Moore) |
| Problem splits into independent subproblems | Divide and Conquer |
| Subproblems overlap, optimal substructure | Dynamic Programming |
| Local optimal → global optimal | Greedy |
| State represented by small set | Bitmask DP |
| Fixed/variable size contiguous subarray | Sliding Window |
| Sorted array, find pair/triplet | Two Pointers |
| Dynamic connectivity, disjoint groups | Union-Find |
| Expected efficiency sufficient | Randomized |
Complexity Comparison¶
| Paradigm | Typical Time | Typical Space | Trade-off |
|---|---|---|---|
| Backtracking | O(b^d) worst, better with pruning | O(d) | Exact solutions, exponential worst |
| D&C | O(n log n) | O(log n) to O(n) | Good for parallelization |
| Two Pointers | O(n) | O(1) | Requires sorted or specific structure |
| Sliding Window | O(n) | O(k) or O(|Σ|) | Contiguous sequences only |
| Union-Find | O(α(n)) per op | O(n) | Dynamic connectivity |
| Randomized | Expected bounds | Varies | May have worst-case issues |