The most important algorithmic patterns
Dynamic Arrays
The standard list in Python is a dynamic array. It supports the operations:
The big things to note are:
lst.pop(0)isO(n)since you’re left-shifting all the elements to right.lst = [x]creates a shallow copy of the list.
lst.pop()removes the rightmost element inO(1)time.x in lstis anO(n)operation that does a linear scan.lst[:]returns a shallow copy oflst.lst.sort()sorts in-place andlst.reverse()reverses in-place.sorted(lst)returns a sorted copy;reversed(lst)is the reversal analogue.
lst[i]accesses elementiandlst[i] = xsets it.- accessing a slice of a list is done by writing
lst[start:end:step];endis an exclusive bound.
- accessing a slice of a list is done by writing
String Manipulation
STL
str.isupper(),str.islower()str.lower(),str.upper()ord('a') = 97&chr(97) = 'a'['a','b','c'].join(",") = 'a,b,c''a,b,c'.split(',') = ['a','b','c']stris immutable;s[:]produces a copy ofs^{convertingstrinto array of chars and joining back avoids copy costs}“
Two Pointers
Bidirectional Pointers
The two pointers start at opposite ends of the array and move inwards terminating at equality.
def two_sum(sorted_arr: list[int], target: int=0) -> list[int] | list[None]:
l, r = 0, len(sorted_arr) - 1
while l < r:
curr = sorted_arr[l] + sorted_arr[r]
if curr < target:
l+=1
elif curr > target:
r-=1
else:
return [l,r]
return [None, None]
Slow & Fast Pointers
The slow and fast pointer each move at unequal though fixed rate through the array.
def find_array_middle(arr: list[int]) -> int | None:
if not arr:
return None
slow = fast = 0
while fast < len(arr) - 1 and fast + 1 < len(arr):
slow += 1
fast += 2
return arr[slow]
Parallel Pointers
Move through one array continuously and moving through the second conditionally.
def is_subset(A: list[int], B: list[int]) -> bool:
i = j = 0
while i < len(A) and j < len(B):
if A[i] == B[j]:
# moving through A indicates
# that the element is common
i += 1
j += 1
return i == len(A)
Binary Search
STL
bisect.bisect(arr, target)is an alias forbisect.right(arr, target)bisect.bisect_left(arr, target)yields the leftmost instance oftargetor the insertion pointbisect.insort_right(bisect.insort) andbisect.insort_leftperform anO(n)insertion after a binary search
The trick with binary search is deciding when to terminate the loop. The algorithm separates the array into two (or three) groups: less than, equal to and greater than.
- 3-way partition:
l<=rfor(values < target, values == target, values > target)
- 2-way partition
l<rfor(values<target, values>=target)r-l>1for finding adjacent elements that signify a transition point
Standard Algorithm
def binary_search(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
m = l + (r - l) // 2
if arr[m] == target:
return m
elif arr[m] < target:
l = m + 1
else:
r = m - 1
return -1
Bisection
def bisect(arr, target, rightmost=False):
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target or (rightmost and arr[mid] == target):
left = mid + 1
else:
right = mid
return left
Transition Point in Shifted Array
def transition(arr):
if arr[0] < arr[-1]:
return 0
l, r = 0, len(arr) - 1
# l is before transition
# r is after transition
# terminate when they're adjacent
while (r - l) > 1:
m = l + (r - l) // 2
if arr[m] < arr[r]:
r = m
else:
l = m
return r
Sets & Maps
Sorting
def merge(left, right):
i, j = 0, 0
merged = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
def mergesort(arr):
n = len(arr)
if n<= 1:
return arr
left = mergesort(arr[:n//2])
right = mergesort(arr[n//2:])
return merge(left, right)
import random
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr)
smaller, equal, larger = [], [], []
for x in arr:
if x<pivot: smaller.append(x)
if x==pivot: equal.append(x)
if x>pivot: larger.append(x)
return quicksort(smaller) + equal + quicksort(larger)
import random
def partition(arr, left, right):
pivot = arr[random.randrange(left, right+1)]
lt, gt = left, right
i = left
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else: # arr[i] == pivot
i += 1
return lt, gt
def quicksort(arr, l=None, r=None):
if not arr:
return []
if l is None:
l = 0
if r is None:
r = len(arr) - 1
if l < r:
lt, gt = partition(arr, l, r)
quicksort(arr, l, lt - 1)
quicksort(arr, gt + 1, r)
return arr
import random
def quickselect(arr, k, l=None, r=None):
if len(arr)==1: return arr[0]
if not l: l = 0
if not r: r = len(arr)-1
lt, rt = partition(arr, l, r)
if lt<=k<=rt:
return arr[k-1] # equal segment
elif k<lt:
r = lt # omit the right
elif k>rt:
l = rt # omit the left
return quickselect(arr, k, l, r)
Stacks & Queues
Stack: FIFO Queue: LIFO
Recursion
Linked Lists
def find_cycle_start(head):
if not head or not head.next:
return None
# Floyd's Tortoise and Hare
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not fast or not fast.next:
return None
# Find Cycle Start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
def remove_kth_node(head, k):
if not head: return None
dummy = Node()
dummy.next = head
for _ in range(k):
fast = fast.next
if fast is None:
return dummy.next
while fast and fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
Trees
from typing import Optional
class BinaryNode:
def __init__(self, val, left: Optional['BinaryNode'], right: Optional['BinaryNode']):
self.val = val
self.left = left
self.right = right
class NAryNode:
def __init__(self, val, children: list['Node'] = []):
self.val = val
self.children = children
BFS and DFS are closely related when you consider the data structures used in the iterative versions of the algorithms:
- DFS uses a LIFO stack and BFS uses a FIFO stack
- DFS goes deep and BFS goes wide
- BFS excels at finding the shortest path in unweighted graphs because it guarantees discovering nodes in order of their distance from the source
- DFS is particularly good at exploring all possible paths, detecting cycles in graphs, and solving maze-like problems where you need to explore branches fully before backtracking
- iterative BFS is preferred since we store all the nodes in a list and we want to minimize stack usage; DFS though (in a balanced tree) prefers recursion because the stack size is
log(n)for balanced trees
DFS for (Binary) Trees
Traversal
Recursive
Null checks can be: done by the node itself (reflexive) or by the parent (hierarchical).
The node checks on recursing whether it is None:
preorder, inorder, postorder = [], [], []
def dfs(root):
if not root:
return
preorder.append(root.val)
dfs(root.left)
inorder.append(root.val)
dfs(root.right)
postorder.append(root.val)
Alternatively, the parent checks before recursion:
preorder, inorder, postorder = [], [], []
def dfs(root):
preorder.append(root.val)
if root.left:
dfs(root.left)
inorder.append(root.val)
if root.right:
dfs(root.right)
postorder.append(root.val)
Iterative
def preorder(root):
result = []
if not root:
return result
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# LIFO Stack
# append node.right first to pop node.left first
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
def inorder(root):
result = []
stack = []
current = root
while stack or current:
# Reach the leftmost node
while current:
stack.append(current)
current = current.left
# Process current node
current = stack.pop()
result.append(current.val)
# Move to the right subtree of current
current = current.right
return result
def postorder(root):
result = []
if not root:
return result
# Two-stack method (easier to remember under pressure)
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node)
if node.left:
s1.append(node.left)
if node.right:
s1.append(node.right)
# Extract from second stack
while s2:
result.append(s2.pop().val)
return result
Tree Traversal Information Flow Patterns
In DFS, data flows:
- DOWN via parameters, i.e. parent -> child.
- UP via return values, i.e. child -> parent.
from typing import Optional
def dfs_path_sum(root: Optional['BinaryNode'], target_sum: int) -> bool:
""" Does a path summing to targetSum exist in this binary tree? """
# Base case: Empty tree
if not root:
return False
# Process Node
remaining_sum = target_sum - root.val
# Base Case: Leaf Node
if not root.left and not root.right:
return remaining_sum == 0
# Recurse on Children
left = dfs_path_sum(root.left, remaining_sum)
right = dfs_path_sum(root.right, remaining_sum)
return left or right
BFS for (Binary) Trees
Traversal
from collections import deque
def bfs_iterative(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
return result
def bfs_recursive(root):
if not root:
return []
result = []
def process_level(nodes):
if not nodes:
return
next_level = []
for node in nodes:
result.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
process_level(next_level)
process_level([root])
return result
Graphs
Graphs are represented as:
- edge lists,
- adjacency lists,
- adjacency matrices, and
- grids.
Graphs can be directed or undirected.
Graph Building
def edges_to_adjacency_list(V: int, edges):
graph = [[] for _ in range(V)]
for (a, b) in edges:
# in an undirected graph,
# edge (a, b) signifies both
# a -> b and b -> a;
graph[a].append(b)
# we can omit this reciprocal
# edge in directed graphs
graph[b].append(a)
An adjacency map can be used when matrix identifiers are not integers. When O(1) lookups for the presence of an edge are necessary, use a defaultdict(set) instead of a defaultdict(list)
class Node:
def __init__(self, value):
self.value = value
from collections import defaultdict
def edges_to_adjacency_map(edges):
graph = defaultdict(list) # defaultdict(set)
for (a, b) in edges:
graph[a].append(b) # graph[a].add(b)
graph[b].append(a) # graph[b].add(a)
An adjacency matrix uses a nested lists where mat[x][y] is true if the edge (x,y) exists. Thus, for a graph of vertices, we consume space. This represenatation is more profitable for dense graphs where there are many edges. An alternative is the sparse matrix which uses a defaultdict(lamba: defaultdict(bool)) to store a ‘sparse’ graph.
from collections import defaultdict
def edges_to_mat(V, edges):
# for weighted graphs, float("inf")/float("-inf") to signify no edge
mat = [[False]*V for _ in range(V)]
# mat = defaultdict(lambda: defaultdict(bool)) <- for sparse matrix
for (a,b) in edges:
mat[a][b] = True # store weight here for weighted graph
mat[b][a] = True # if undirected
Traversal: Unweighted Graphs
DFS for Graphs
from collections import defaultdict
def dfs(graph: defaultdict[list], start: int):
visited = {start}
def visit(node):
#process node
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
visit(nbr)
visit(start)
from collections import defaultdict
def count_connected_components(graph: defaultdict[list]):
def visit(src):
visited.add(src)
for nbr in graph[src]:
if nbr not in visited:
visit(nbr)
# Get vertex set.
nodes=set(graph.keys())
for parent in graph:
nodes|=set(graph[parent])
components = 0
visited = set()
for node in nodes:
if node not in visited:
visit(node)
components+=1
return components
BFS for Graphs
from collections import deque
def bfs(graph, start):
""" Shortest path from start to all other nodes in UNWEIGHTED graph"""
q = deque([start])
distances = {start: 0}
""" if we are given multiples sources, we add to q and set each to a distance of 0"""
while q:
for _ in range(len(q)):
curr = q.popleft()
for nbr in graph[curr]:
if nbr not in distances:
distances[nbr] = distances[curr]+1
q.append(nbr)
Djikstra’s - Shortest Path for Positive Weighted Graphs
This is basically BFS using a min-heap priority queue to pick the next lowest weight node to explore.
import heapq
def dijkstra(graph, start):
""" Shortest path from start to all other nodes in WEIGHTED graph"""
pq = [(0, start)] # (distance, node)
distances = {start: 0}
""" if we are given multiple sources, we add to pq and set each to a distance of 0"""
while pq:
dist, curr = heapq.heappop(pq)
# Skip if we've already found a better path
if dist > distances.get(curr, float('inf')):
continue
for nbr, weight in graph[curr]:
new_dist = dist + weight
if nbr not in distances or new_dist < distances[nbr]:
distances[nbr] = new_dist
heapq.heappush(pq, (new_dist, nbr))
return distances
Grids
- Do NOT write
[[0] * num_cols] * num_rows.- Instead:
[[0] * num_cols for _ in range(num_rows)]
- Instead:
- copying a grid:
[row.copy() for row in grid]
grid = [[1]*10 for _ in range(10)]
nr, nc = len(grid), len(grid[0])
def is_valid(cx, cy):
return (
0<=cx<nr and # row boundary condition
0<=cy<nc and # column boundary condition
grid[cx][cy]==1 # valid move?
)
def neighbors(x, y):
offsets = [(0,1), (0,-1), (1,0), (-1,0)]
for dx,dy in offsets:
cx,cy = x+dx, y+dy
if is_valid(cx, cy):
yield (cx, cy)
Traversal
DFS for Graphs as Grids
def grid_dfs(grid, start_r, start_c):
nr, nc = len(grid), len(grid[0])
visited = {(start_r, start_c)}
def is_valid(cx, cy):
return (
0<=cx<nr and # row boundary condition
0<=cy<nc and # column boundary condition
(cx, cy) not in visited and # check if visited
grid[cx][cy]=="#######" # valid move?
)
def neighbors(x, y):
offsets = [(0,1), (0,-1), (1,0), (-1,0)]
for dx,dy in offsets:
cx,cy = x+dx, y+dy
if is_valid(cx, cy):
yield (cx, cy)
def visit(r, c):
# process current location
for cr, cc in neighbors(r, c):
visited.add((cr, cc))
visit(cr, cc)
visit(start_r, start_c)
return
BFS for Graphs as Grids
from collections import deque
def grid_bfs(grid, src, dest):
srcx, srcy = src
destx, desty = dest
nr, nc = len(grid), len(grid[0])
# Edge case: start or end cell is blocked
if (grid[srcx][srcy] == 1 or grid[destx][desty] == 1:
return -1
def is_valid(r, c):
return (
0 <= r < nr and # row boundary
0 <= c < nc and # column boundary
grid[r][c] == 0 # unvisited and valid move
)
def neighbors(r, c):
directions = [
(-1, 0), # Up
(1, 0), # Down
(0, 1), # Right
(0, -1), # Left
(-1, 1), # Up-right
(-1, -1), # Up-left
(1, 1), # Down-right
(1, -1) # Down-left
]
for dr, dc in directions:
cr, cc = r + dr, c + dc
if is_valid(cr, cc):
yield (cr, cc)
# BFS
queue = deque([(0, 0, 1)]) # (row, col, distance)
grid[srcx][srcy] = 1
# BFS
while queue:
r, c, dist = queue.popleft()
# Check if we've reached the target
if r == nr-1 and c == nc-1:
return dist
# Process neighbors
for cr, cc in neighbors(r, c):
grid[cr][cc] = 1 # Mark as visited immediately
queue.append((cr, cc, dist + 1))
return -1
Matrices
Heaps
Heaps: Neither LIFO nor FIFO. They enable access to the next element in order of priority.
Array-Based Heap
import heqpq
array = [2,1,6,7,8,1,3,4,5]
heapq.heapify(array)
heapq.heappop(array) # removes and returns array min
heapq.heappush(array, 9) # adds 9 to the heap
heapq.heappushpop(array, 9) # pushes then pop
heapq.heapreplace(array, 9) # pop then push
def heapsort(array):
h = []
for val in array:
heapq.heappush(h, val)
return [heapq.heappop(h) for _ in range(len(h))]
def parent(idx):
if idx==0: # root
return -1
return (idx-1) // 2
def left_child(idx):
return 2*idx + 1
def right_child(idx):
return 2*idx + 2
class Heap:
def __init__(self, sort_order = lambda x,y: x<y, heap=None):
self.heap = heap or []
self.higher_priority = sort_order
self.heapify()
def size(self):
return len(self.heap)
def top(self):
if not self.heap:
return None
return self.heap[0]
def put(self, elem):
self.heap.append(elem)
self.bubble_up(len(self.heap)-1)
def bubble_up(self, idx):
if idx==0: return
parent_idx = parent(idx)
if self.higher_priority(self.heap[idx], self.heap[parent_idx]):
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
self.bubble_up(parent_idx)
def pop(self):
if not self.heap: return None
top = self.heap[0]
if len(self.heap) == 1:
self.heap = []
return top
self.heap[0] = self.heap[-1]
self.heap.pop()
self.bubble_down(0)
return top
def bubble_down(self, idx):
l_i, r_i = left_child(idx), right_child(idx)
is_leaf = l_i >= len(self.heap)
if is_leaf: return
child_i = l_i
if (
r_i < len(self.heap) and
self.higher_priority(self.heap[r_i], self.heap[l_i])
):
child_i = r_i
if self.higher_priority(self.heap[child_i], self.heap[idx]):
self.heap[idx], self.heap[child_i] = self.heap[child_i], self.heap[idx]
self.bubble_down(child_i)
def heapify(self):
for idx in range(len(self.heap)//2, -1, -1):
self.bubble_down(idx)
Sliding Windows
def minimum_window(arr):
initialize:
- l and r to 0 (empty window)
- data structures to track window info
- set cur_best
while true
if window growth condition holds:
if the window cannot grow (r == len(arr))
break
grow the window (update data structures and increase r)
else
update cur_best if needed
shrink the window (update data structures and increase l)
return cur_best
Backtracking
Backtracking is implementing a DFS search over a decision tree. Model a set of decisions as a tree, and run DFS over the tree. As you find a branch that is not viable, prune it and terminate search.
Combinatorial Enumeration
Combinations / Subsets / Unordered
def subsets_without_repetition(nums):
def dfs(slate, partial, results):
if slate==len(nums):
results.append(partial[:])
else:
results = dfs(slate+1, partial, results) # left recursion
results = dfs(slate+1, partial+[nums[slate]], results) # right recursion
return results
return dfs(0, [], [])
def subsets_with_repetition(nums, k):
def dfs(partial, results, k):
if len(partial)==k:
results.append(partial[:])
else:
for i in range(len(nums)):
# at each step choose a value from nums
results = dfs(partial+[nums[i]], results, k)
return results
return dfs([], [], k)
Permutations / Orderings
def permutations_without_repetition(arr):
res = []
perm = arr[:]
def visit(i):
# visiting i means you're choosing a value
# to slot into position i
if i == len(perm) - 1:
res.append(perm[:])
return
# you've already slotted values for 0 to i-1
# so choose an option from i+1 onwards
for j in range(i, len(perm)):
perm[i], perm[j] = perm[j], perm[i]
visit(i + 1)
perm[i], perm[j] = perm[j], perm[i]
visit(0)
return res
permutations_without_repetition([0,1,2,3])
Dynamic Programming
Greedy Algorithms
Topological Sort
A DAG, a directed acyclic graph, ia a directed graph without cycles. DAG <=> Topologically Sortable.
DAG Problem Types:
- Is this a DAG?
- Try to top-sort it (via Kahn’s Algorithm). 1[1] DFS can also be used, but it’s finicky.
- top-sort an edge list.
- Find shortest / longest path in DAG (even with negative weights).
- How many topological orderings are there?
- At each
order nodesstep while top-sorting via Kahn’s, count the number of options.- Then it’s a counting problem, i.e. you have
nnodes inzeros, so n! ways of ordering those zero in-degrees. In the next iteration, if youmnodes in zeros, that would meanm!orderings of that level. So a total ofn!*m!orders of these two levels.
- Then it’s a counting problem, i.e. you have
- At each
Kahn’s Topological Sort
def top_sort(graph):
V = len(graph)
# Compute in_degree
in_degrees = [0 for _ in range(V)]
for src in range(V):
for dest in graph[src]: # Weighted Graphs: dest, weight
in_degrees[dest]+=1
# identify 0-degree nodes
zeros = []
for node in range(V):
if in_degrees[node]==0:
zeros.append(node)
# OR: zeros = [node for node in range(V) if in_degrees[node]==0]
# order nodes
ordering = []
while zeros:
for _ in range(len(zeros)):
# this is useful for processing by groups of options
# each group can be reordered into any of its permutations
# and still produce a valid top sort,
# i.e. factorial(len(zeros)) orders exist per group
src = zeros.pop() # you could use any 0-in_degree node, so pop from the left.
ordering.append(src)
for dest in graph[src]: # Weighted Graphs: dest, weight
in_degrees[dest]-=1
if in_degrees[dest]==0:
zeros.append(dest)
if len(ordering)<V:
return [] # Cyclic Graph
return ordering
def longest_path(graph, start):
ordering = top_sort(graph)
if not ordering:
return [] # Cyclic Graph
lengths = {i: float("-inf") for i in range(len(graph))}
lengths[start] = 0
for node in ordering:
if lengths[node] == float("-inf"): continue
for nbr, weight in graph[node]:
if lengths[node] + weight > lengths[nbr]:
lengths[nbr] = lengths[node] + weight
return [lengths[i] for i in range(len(graph))]
Prefix Sums
Monotonic Stacks & Queues
Set & Map Implementations
Advanced Dynamic Programming
Union Find
This data structure implements three primary functions find, union, and add. 1. find(x) returns the representative element of the set that contains x. 2. union(x, y) merges the groups containing x and y. 3. add(x) creates a set in the data structure with the set representativex.
class UnionFind:
def __init__(self):
self.parent = dict()
def add(self, x):
self.parent[x] = x
def find(self, x):
root = self.parent[x]
while self.parent[root] != root:
root = self.parent[root]
return root
def union(self, x, y):
repr_x, repr_y = self.find(x), self.find(y)
if repr_x == repr_y:
return # They are already in the same set.
self.parent[repr_x] = repr_y
class PathCompression(SuboptimalUnionFind):
def find(self, x):
root = self.parent[x]
while self.parent[root] != root:
root = self.parent[root]
while x != root:
self.parent[x], x = root, self.parent[x]
return root
class UnionBySize(SuboptimalUnionFind):
def __init__(self):
super().__init__()
self.size = dict()
def add(self, x):
super().add(x)
self.size[x] = 1
def union(self, x, y):
repr_x, repr_y = self.find(x), self.find(y)
if repr_x == repr_y:
return
if self.size[repr_x] < self.size[repr_y]:
self.size[repr_y] += self.size[repr_x]
self.parent[repr_x] = repr_y
else:
self.size[repr_x] += self.size[repr_y]
self.parent[repr_y] = repr_x
class UnionFind(PathCompression, UnionBySize):
def __init__(self):
super().__init__()
Kruskal’s Minimum Spanning Tree
def kruskal(V, edges): # connected graph with weighted edges
uf = UnionFind()
for u in range(V):
uf.add(u)
mst_cost = 0
edges.sort(key=lambda edge: edge[2])
for u, v, weight in edges:
repr_u, repr_v = uf.find(u), uf.find(v)
if repr_u != repr_v:
uf.union(u, v)
mst_cost += weight
return mst_cost