LeetCode
This cheatsheet covers the algorithms and data structures required to solve the majority of LeetCode problems. Please contact me for corrections/omissions. An accompanying Anki Deck is provided.
Last updated: 1 July 2024
Problem Solving1
- Listen carefully.
- Draw an example that is sufficiently large and not a special case.
- State the brute-force solution.
- Optimize, looking for BUD (Bottlenecks, Unnecessary Work, Duplicated Work).
- Walk through approach in detail.
- Implement solution using modular code, error checks, and good variables names.
- Test hot spots, special cases, and conceptually walking through the code line-by-line.
Complexity
\(O\)-notation, \(\Omega\)-notation, \(\Theta\)-notation
- \(O\)-notation provides an upper bound for the amount of time or space an algorithm will consume for any input of size \(n\).
- \(\Omega\)-notation provides a lower bound for the amount of time or space an algorithm will consume for any input of size \(n\).
- \(\Theta\)-notation provides a tight bound for the amount of time or space an algorithm will consume for any input of size \(n\).
O(n!) O(2n) O(n2) O(n log n) O(n) O(log n) O(1)
Best Case, Worst Case, Average Case
- Best Case: minimum amount of time or space an algorithm will consume for the most favorable input of size \(n\).
- Worst Case: maximum amount of time or space an algorithm will consume for any possible input of size \(n\).
- Average Case: expected amount of time or space an algorithm will consume when all possible inputs of size \(n\) are equally likely.
Amortized Running Time
Allows us to describe that, yes, this worst case happens every once in a while. But once it happens, it won’t happen again for so long that the cost is “amortized”.
Recursive Running Time
Running time for recursive functions will often look like \(O(\textrm{branches}^\textrm{depth})\).
Algorithms
An algorithm is a sequence of computational steps that transform the input into the output.2
Algorithms: Backtracking
A backtracking algorithm finds all (or some) solutions to a problem by incrementally building candidates to the solutions. As soon as it determines that a candidate cannot lead to a final solution, it abandons the candidate (“backtracking”). Typically, problems that ask you to find all of something with low bounds can be solved with backtracking.
def backtrack(path, choices):
if is_solution(path):
result.append(path[:])
return
for choice in choices:
if not is_valid(choice):
continue
# Make the choice
path.append(choice)
new_choices = None # update choices
backtrack(path, new_choices)
# Undo the choice (backtrack)
path.pop()
result = []
initial_path = []
initial_choices = get_initial_choices()
backtrack(initial_path, initial_choices)
Patterns
Key Problems
- Medium Generate Parentheses
- Hard N-Queens
- Hard Sudoku Solver
Subsets
- Medium Permutations
- Medium Subsets
- Medium Subsets II
Algorithms: Bit Manipulation
Bitwise Operators
NOT ~
Unary operation that returns the complement of x
by flipping all the bits (0 becomes 1, and 1 becomes 0).
AND &
Binary operation that returns a new number where each bit is set only if both corresponding bits in x
and y
are 1.
OR |
Binary operation that returns a new number where each bit is set if at least one of the corresponding bits in x
or y
is 1.
XOR ^
Binary operation that returns a new number where each bit is set if the corresponding bits in x
and y
are different (i.e. one is 1 and the other is 0).
Bit Shifts
- Arithmetic shift: when bits are shifted left, zeros are filled in on the right (same as logical shift), but when bits are shifted right, the sign bit is replicated to fill in the empty spaces.
x << y
is the same as multiplyx
by \(2^y\).x >> y
is the same as//
-ingx
by \(2^y\). - Logical shift: when bits are shifted left or right, empty spaces are filled with zeros.
- Circular shift: when bits are shifted left or right, bits that fall off are wrapped around.
Boolean Algebra
- AND
x & 0s = 0
x & 1s = x
x & x = x
- OR
x | 0s = x
x | 1s = 1s
x | x = x
- XOR
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0
Two’s Complement1
Computers typically store integers in two’s complement representation. A positive number is represented as itself while a negative number is represented as the two’s complement of its absolute value (with a 1 in its sign bit to indicate a negative value). The binary representation of \(-K\) as a \(N\)-bit number is concat(1, 2^(N-1) - K)
. Two’s complement allows the use of the same hardware circuitry for both addition and subtraction.
Common Operations
def get_bit(num: int, i: int) -> int:
return (num >> i) & 1
def set_bit(num: int, i: int) -> int:
return num | (1 << i)
def clear_bit(num: int, i: int) -> int:
return num & ~(1 << i)
def update_bit(
num: int,
i: int,
bit_is_1: bool,
) -> int:
value = 1 if bit_is_1 else 0
mask = ~(1 << i)
return (num & mask) | (value << i)
Patterns
Key Problems
- Easy Add Binary
- Easy Missing Number
- Medium Sum of Two Integers
Bitwise XOR
Use Bitwise XOR to solve problems.
- Easy Complement of Base 10 Integer
- Easy Single Number
- Medium Single Number II
Algorithms: Cascading
A cascading algorithm can be used when all possible subsets (the power set) are required. While backtracking builds and discards partial solutions on the fly, cascading typically generates all intermediate states and stores them, resulting in higher space complexity.
def subsets_backtracking(
nums: List[int]
) -> List[List[int]]:
def backtrack(path, start):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(path, i + 1)
path.pop()
result = []
backtrack([], 0)
return result
def subsets_cascading(
nums: List[int]
) -> List[List[int]]:
results = [[]]
for num in nums:
results.extend([result + [num]
for result in results])
return results
Algorithms: Dynamic Programming21
A dynamic programming algorithm improves on a recursive approach by finding overlapping subproblems and caching the result.
There are two equivalent ways of solving a Dynamic Programming problem:
- Top-Down (Memoization): Write the recursive solution and use a data structure (like an array or hash table) to save the result of each subproblem so that each subproblem is only computed once.
- Bottom-Up (Tabulation): Starting at the base cases, iteratively fill up a table in a way that depends on the already filled entries (solving smaller subproblems first). While this approach can be less space-efficient, potentially computing and storing unnecessary states, techniques like rolling arrays or state reduction can optimize space usage.
A problem is a good candidate for Dynamic Programming if: (i) it asks for the optimum value (e.g. max, min, longest, shortest) of something or the number of ways to do something or if it is possible to reach a certain point; and (ii) future decisions depend on earlier decisions, e.g. using one element prevents the usage of other elements.
Steps for Solving Dynamic Programming Problems
- Solve using recursion
- Apply memoization
- Pass arguments by reference instead of by value
- Replace recursion with iteration and use a table instead of memoization
Example: Fibonacci Sequence
cache = dict()
def fib_top_down(n: int) -> int:
global cache
if n == 0 or n == 1:
return 1
if n in cache:
return cache[n]
cache[n] = (fib_top_down(n - 1) +
fib_top_down(n - 2))
return cache[n]
def fib_bottom_up(n: int) -> int:
ans = [1, 1]
while len(ans) <= n:
ans.append(ans[-1] + ans[-2])
return ans[n]
Patterns
1-Dimensional
- Medium Coin Change
- Medium Longest Increasing Subsequence
- Medium Maximum Subarray
2-Dimensional
- Medium Edit Distance
- Medium Longest Common Subsequence
- Medium Unique Paths
Algorithms: Greedy
A greedy algorithm builds a solution piece-by-piece, always making a choice that looks the best at the moment and never takes back its choices. It assembles a globally optimal solution by making locally optimal (greedy) choices. Greedy algorithms are often simpler and faster than other approaches like dynamic programming, but they require a proof of correctness to ensure they work for the given problem.
Patterns
Key Problems
- Medium Container With Most Water
- Medium Jump Game
- Medium Jump Game II
Algorithms: Sorting
Bubble Sort
Best: O(n) Average: O(n2) Worst: O(n2) Space: O(1)
Repeatedly compare and swap adjacent elements if they are in the wrong order, effectively “bubbling” the largest unsorted element to its correct position with each full pass through the list.
def bubble_sort(A: list[int]) -> None:
n = len(A)
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# Bubble item up to final position
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
Heapsort
Best: O(n log n) Average: O(n log n) Worst: O(n log n) Space: O(1)
Construct a binary heap from the data and repeatedly removes the largest element from the heap, rebuilding the heap each time, to achieve a sorted list.
def max_heapify(
A: list[int],
n: int,
i: int,
) -> None:
largest = i # initialize largest as root
left = 2 * i + 1
right = 2 * i + 2
# See if left child of root exists and
# is greater than root
if left < n and A[left] > A[largest]:
largest = left
# See if right child of root exists and
# is greater than root
if right < n and A[right] > A[largest]:
largest = right
# Change root, if needed
if largest != i:
A[i], A[largest] = A[largest], A[i]
# Heapify the root
max_heapify(A, n, largest)
def build_max_heap(A: list[int]) -> None:
n = len(A)
for i in range(n // 2 - 1, -1, -1):
max_heapify(A, n, i)
def heapsort(A: list[int]) -> None:
n = len(A)
# Build a max heap from the input array
build_max_heap(A, n)
# One by one extract elements from the heap
for i in range(n - 1, 0, -1):
# Move current root to end
A[i], A[0] = A[0], A[i]
# Call max_heapify on the reduced heap
max_heapify(A, i, 0)
Insertion Sort
Best: O(n) Average: O(n2) Worst: O(n2) Space: O(1)
Build the final sorted array one item at a time, inserting each new element into its appropriate position within the already sorted portion of the array.
def insertion_sort(A: list[int]) -> None:
for i in range(1, len(A)):
key = A[i]
# Insert into sorted subarray A[0..i-1]
j = i - 1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j -= 1
A[j+1] = key
Merge Sort
Best: O(n log n) Average: O(n log n) Worst: O(n log n) Space: O(n)
Recursively divide the list into halves, sorting each half, and merging the sorted halves back together.
def merge(
A: list[int],
p: int,
q: int,
r: int,
) -> None:
# Create left and right subarrays
L = A[p:q+1]
R = A[q+1:r+1]
# Initial indexes for left (i),
# right (j) and merged array (k)
i = j = 0
k = p
# Merge the temp arrays back into A[p..r]
while i < len(L) and j < len(R):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L, if any
while i < len(L):
A[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R, if any
while j < len(R):
A[k] = R[j]
j += 1
k += 1
def merge_sort(
A: list[int],
p: int,
r: int,
) -> None:
if p >= r: # zero or one element?
return
q = (p + r) // 2 # mid-point of A[p:r]
merge_sort(A, p, q)
merge_sort(A, q + 1, r)
# Merge A[p:q] and A[q+1:r] into A[p:r]
merge(A, p, q, r)
Quicksort
Best: O(n log n) Average: O(n log n) Worst: O(n2) Space: O(log n)
Select a “pivot” element and partition the array into sub-arrays containing elements less than and greater than the pivot, then recursively apply the same strategy to each sub-array.
def partition(
A: list[int],
p: int,
r: int,
) -> int:
pivot = A[r] # choose last item as pivot
i = p - 1 # highest index into low side
# Process each element other than the pivot
for j in range(p, r):
# Does element belong on low side?
if A[j] <= pivot:
# Index of new slot on low side
i += 1
# Put element there
A[i], A[j] = A[j], A[i]
# Pivot goes just to the right of low side
A[i + 1], A[r] = A[r], A[i + 1]
return i + 1 # new index of the pivot
def quicksort(
A: list[int],
p: int,
r: int,
) -> None:
if p < r:
# Partition the subarray around the pivot, which ends up in A[q]
q = partition(A, p, r)
quicksort(A, p, q - 1) # recursively sort the low side
quicksort(A, q + 1, r) # recursively sort the high side
Data Structures
A data structure is a way to store and organize data in order to facilitate access and modifications.2
Data Structures: Array
A collection of elements, of same memory size, each identified by an array index.
Complexity
Average Case
Access: O(1) Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Worst Case
Access: O(1) Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Algorithms
Boyer-Moore Majority Vote Algorithm
Best: O(n) Average: O(n) Worst: O(n) Space: O(1)
Use a pair-wise cancellation strategy to identify the majority element.
def majority_vote(nums: list[int]) -> int:
count = 0
candidate = None
for num in nums:
if count == 0:
# Forget previous runs
candidate = num
# count majority element instances as +1
# count other element instances as -1
count += (1 if num == candidate else -1)
return candidate
Fisher-Yates Shuffle Algorithm
Best: O(n) Average: O(n) Worst: O(n) Space: O(1)
Randomly permute a list by iteratively swapping each element with a random element that has not been shuffled yet, ensuring each permutation is equally likely.
def shuffle(arr: list[int]) -> None:
n = len(arr)
# Loop from 0 to n-2
for i in range(n - 1):
# Generate a random index from i to n-1
j = random.randint(i, n - 1)
# Swap the elements at indices i and j
arr[i], arr[j] = arr[j], arr[i]
Kadane’s Maximum Subarray Algorithm
Best: O(n) Average: O(n) Worst: O(n) Space: O(1)
Use a rolling sum that resets when negative to find the largest sum of any contiguous subarray.
def max_subarray(arr: list[int]) -> int:
best_sum = -float("inf")
current_sum = 0
for x in arr:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
Rabin-Karp String Matching Algorithm
Best: O(n+m) Average: O(n+m) Worst: O(n·m) Space: O(1)
Use a rolling hash function to efficiently search for pattern matches in text, allowing for quick hash comparisons and re-computation of hashes when moving the search window.
def string_match(text: str, pattern: str) -> list[int]:
n = len(text)
m = len(pattern)
d = 256 # number of characters in alphabet
q = 101 # prime number
h = pow(d, m-1) % q # highest-order digit
p = 0 # hash value for pattern
t = 0 # hash value for text
# Calculate hash value of pattern and first window of text
for i in range(m):
p = (d * p + ord(pattern[i])) % q
t = (d * t + ord(text[i])) % q
# Slide the pattern over the text one by one
shifts = []
for s in range(n - m + 1):
# Check hash values of pattern and current window of text
if p == t:
# Check actual characters one by one
if text[s:s+m] == pattern:
shifts.append(s)
# Calculate the hash value for the next window of text:
# Remove the leading digit, add the trailing digit
if s < n - m:
t = (d * (t - ord(text[s]) * h) + ord(text[s + m])) % q
# Convert negative hash to positive
if t < 0:
t += q
return shifts
Patterns3
Binary Search
Use a modified version of binary search.
- Easy Binary Search
- Easy Find Smallest Letter Greater Than Target
- Medium Search in Rotated Sorted Array
def bisect_left(a, x):
# Locate insertion point for x in sorted a
# left of any existing entries of x in a.
left = 0
right = len(a) - 1
while left <= right:
mid = left + (right - left) // 2
if a[mid] < x:
left = mid + 1
else:
right = mid - 1
return left
def bisect_right(a, x):
# Locate insertion point for x in sorted a
# right of any existing entries of x in a.
left = 0
right = len(a) - 1
while left <= right:
mid = left + (right - left) // 2
if a[mid] <= x:
left = mid + 1
else:
right = mid - 1
return left
def index_left(a, x):
# Locate leftmost value exactly equal to x
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def index_right(a, x):
# Locate rightmost value exactly equal to x
i = bisect_right(a, x)
if i and a[i-1] == x:
return i-1
raise ValueError
def find_lt(a, x):
# Locate rightmost value less than x
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
# Locate rightmost value less than or equal to x
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
# Locate leftmost value greater than x
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
# Locate leftmost item greater than or equal to x
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError
Intervals
Merge overlapping intervals.
- Medium Insert Interval
- Medium Interval List Intersections
- Medium Merge Intervals
Sliding Window
Create a window into the array and move it around to gather specific information.
- Easy Best Time to Buy and Sell Stock
- Medium Longest Substring Without Repeating Characters
- Hard Minimum Window Substring
Two Pointers
Use two pointers to traverse an array from different ends or directions.
- Medium 3Sum
- Medium Container With Most Water
- Easy Valid Palindrome
Data Structures: Binary Search Tree
A binary tree where the key of each internal node being greater than all the keys in the respective node’s left subtree and less than the ones in its right subtree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key: int) -> None:
if self.root is None:
self.root = TreeNode(key)
else:
self._insert(self.root, key)
def _insert(self, node: TreeNode, key: int) -> None:
if key < node.val:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert(node.left, key)
elif key > node.val:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert(node.right, key)
def delete(self, key: int) -> None:
self.root = self._delete(self.root, key)
def _delete(self, node: TreeNode, key: int) -> TreeNode:
if node is None:
return node
if key < node.val:
node.left = self._delete(node.left, key)
elif key > node.val:
node.right = self._delete(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
min_larger_node = self._find_min(node.right)
node.val = min_larger_node.val
node.right = self._delete(node.right, min_larger_node.val)
return node
def _find_min(self, node: TreeNode) -> TreeNode:
while node.left is not None:
node = node.left
return node
def search(self, key: int) -> bool:
return self._search(self.root, key)
def _search(self, node: TreeNode, key: int) -> bool:
if node is None:
return False
elif key == node.val:
return True
elif key < node.val:
return self._search(node.left, key)
else:
return self._search(node.right, key)
Algorithms
Pre-Order Traversal (Recursive)
def traverse(root: TreeNode) -> list[TreeNode]:
if not root:
return []
return ([root.val] +
traverse(root.left) +
traverse(root.right))
Pre-Order Traversal (Iterative)
def traverse(root: TreeNode) -> list[TreeNode]:
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
In-Order Traversal (Recursive)
def traverse(root: TreeNode) -> list[TreeNode]:
if not root:
return []
return (traverse(root.left) +
[root.val] +
traverse(root.right))
In-Order Traversal (Iterative)
def traverse(root: TreeNode) -> list[TreeNode]:
result = []
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.val)
node = node.right
return result
Post-Order Traversal (Recursive)
def traverse(root: TreeNode) -> list[TreeNode]:
if not root:
return []
return (traverse(root.left) +
traverse(root.right) +
[root.val])
Post-Order Traversal (Iterative)
def traverse(root: TreeNode) -> list[TreeNode]:
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return reversed(result)
Complexity
Average Case
Search: O(log n) Insert: O(log n) Delete: O(log n) Space: O(n)
Worst Case
Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Patterns
Breadth-first Search
Traverse tree level-by-level.
- Medium Binary Tree Level Order Traversal
- Medium Binary Tree Right Side View
- Medium Binary Tree Zigzag Level Order Traversal
Depth-first Search
Traverse tree depth-wise.
Data Structures: Graph
A collection of nodes and edges. Edges can be directed and have weights.
type Graph = dict[int, dict[int, float]]
def add_vertex(
graph: Graph,
v: int,
) -> None:
if v not in graph:
graph[v] = {}
def remove_vertex(
graph: Graph,
v: int,
) -> None:
if v in graph:
# Remove the vertex
del graph[v]
# Remove all edges to this vertex
for edges in graph.values():
if vertex in edges:
del edges[vertex]
def add_edge(
graph: Graph,
u: int,
v: int,
weight: float,
) -> None:
if u not in graph:
graph[u] = {}
graph[u][v] = weight
def remove_edge(
graph: Graph,
u: int,
v: int,
) -> None:
if u in graph and v in graph[u]:
del graph[u][v]
Minimum Spanning Tree
A subgraph that connects all the vertices in the original graph with no cycles and exactly \(n-1\) edges, while minimising total edge weight.
Algorithms
Bellman-Ford’s Single-Source Shortest Path Algorithm
Best: O(V·E) Average: O(V·E) Worst: O(V·E) Space: O(V)
Relax edges repeatedly to find the shortest path from a single source to all other vertices, effectively handling graphs with negative weight edges.
def bellman_ford(
graph: Graph,
source: int,
) -> dict[int, float] | None:
# Initialize distances
dist = {u: float('inf') for u in graph}
dist[source] = 0
# Relax edges repeatedly
for _ in range(len(graph) - 1):
for u in graph:
for v, weight in graph[u].items():
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# Check for negative-weight cycles
for u in graph:
for v, weight in graph[u].items():
if dist[u] + weight < dist[v]:
# Error: Negative weight cycle
return None
return dist
Dijkstra’s Single-Source Shortest Path Algorithm
Best: O(V+E·log V) Average: O(V+E·log V) Worst: O(V+E·log V) Space: O(V)
Use a priority queue to greedily select the nearest vertex not yet processed and perform relaxations efficiently. This algorithm doesn’t handle graphs with negative weights.
from heapq import heappush, heappop
def dijkstra(
graph: Graph,
source: int,
) -> dict[int, float]:
# Initialize all distances with infinity
dist = {u: float('inf') for u in graph}
dist[source] = 0
# Previous node in optimal path
prev = {u: None for u in graph}
# Priority queue: (curr_dist, vertex)
min_heap = [(0, source)]
while min_heap:
curr_dist, u = heappop(min_heap)
# Skip if there's already a better way
if curr_dist > dist[u]:
continue
for v, weight in graph[u]:
alt = curr_dist + weight
# Only consider new path if better
if alt < dist[v]:
dist[v] = alt
prev[v] = u
heappush(min_heap, (alt, v))
return dist
Floyd–Warshall’s All-Pairs Shortest Path Algorithm
Best: O(V3) Average: O(V3) Worst: O(V3) Space: O(V2)
Dynamically calculate shortest paths between all pairs of vertices using a matrix-based approach, leveraging the principle of transitivity.
def floyd_warshall(graph: Graph) -> dict[int, dict[int, float]]:
# Initialize distances with infinity
dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
# Set edges to weight
for u in graph:
for v, weight in graph[u].items():
dist[u][v] = weight
# Set diagonals to zero
for v in graph:
dist[v][v] = 0
# Floyd-Warshall algorithm
for k in graph:
for i in graph:
for j in graph:
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Kahn’s Directed Acyclic Graph Topological Sort Algorithm
Best: O(V+E) Average: O(V+E) Worst: O(V+E) Space: O(V)
Use in-degree counts to find a “safe” order of nodes such that every node appears before its successors.
from collections import deque
def kahn_topological_sort(
graph: Graph,
) -> list[int] | None:
# Calculate in-degrees of each node
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# Queue of all vertices with in-degree 0
queue = deque([u for u in graph
if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
# Decrease in-degree of each neighbor
# and check if it becomes zero
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# Check there was no cycle in the graph,
# i.e., all edges are removed
if len(top_order) == len(in_degree):
return top_order
else:
# Error: Cycle detected in graph
return None
Kruskal’s Minimum Spanning Tree Algorithm
Best: O(E·log V) Average: O(E·log V) Worst: O(E·log V) Space: O(V)
Add edges in increasing weight order to a growing forest, using a Union-Find data structure to avoid cycles.
def kruskal_mst(
graph: Graph,
) -> set[tuple[int, int]]:
uf = UnionFind(len(graph))
mst = set()
# Sort edges by weight
edges = [u, v, graph[u][v]
for u in graph
for v in graph[u]]
edges.sort(key=lambda x: x[2])
for u, v, weight in edges:
if not uf.connected(u, v):
mst.add((u, v))
uf.union(u, v)
return mst
Prim’s Minimum Spanning Tree Algorithm
Best: O(E·log V) Average: O(E·log V) Worst: O(E·log V) Space: O(V)
Grow the minimum spanning tree by starting from an arbitrary vertex and greedily adding the least weight edge connecting the tree to another vertex.
from heapq import heappush, heappop
def prim_mst(
graph: Graph,
start: int,
) -> set[tuple[int, int]]:
parent = {u: None for u in graph}
key = {u: float('inf') for u in graph}
# No cost to begin from start vertex
key[start] = 0
# Fill priority queue with all vertices
min_heap = []
for v in graph:
heappush(min_heap, (key[v], v))
visited = set()
while min_heap:
# Extract vertex with minimum key
_, u = heappop(min_heap)
if u in visited:
continue
else:
visited.add(u)
# Process all adjacent vertices of u
for v, weight in graph[u].items():
if v in visited:
continue
if weight < key[v]:
parent[v] = u
key[v] = weight
# Instead of decrease-key, push
# new key with vertex to queue
heappush(min_heap, (weight, v))
# Prepare result edges from parent map
mst = [(parent[v], v, key[v])
for v in parent
if parent[v] is not None]
return mst
Hierholzer’s Eulerian Path Algorithm
Best: O(E) Average: O(E) Worst: O(E) Space: O(V+E)
Build an Eulerian Path by repeatedly finding and merging cycles within the graph until all edges are included in a single path.
A* Pathfinding Algorithm
Best: O(E) Average: O(E) Worst: O(E) Space: O(V)
Combine heuristics with Dijkstra’s algorithm to efficiently find the shortest path, prioritizing paths that appear to lead directly to the goal.
from heapq import heappush, heappop
def a_star(
graph: Graph,
start: int,
goal: int,
h: Callable[[int, int], float],
) -> tuple[dict[int, float], dict[int, int]]:
# Initialize all distances with infinity
dist = {u: float('inf') for u in graph}
dist[start] = 0
# Previous node in optimal path
prev = {u: None for u in graph}
# Priority queue:
# (est_cost, curr_dist, vertex)
min_heap = [(h(start, goal), 0, start)]
while min_heap:
_, curr_dist, u = heappop(min_heap)
# Early exit if reaching the goal
if u == goal:
return dist, prev
for v, weight in graph[u].items():
alt = curr_dist + weight
if alt < dist[v]:
dist[v] = alt
prev[v] = u
est_cost = alt + h(v, goal)
item = (est_cost, alt, v)
heappush(min_heap, item)
return dist, prev
def h(v: int, goal: int) -> float:
# Heuristic function estimating the cost to
# reach goal from vertex v
return abs(goal - v) # Manhattan distance
Patterns
Key Problems
- Medium Cheapest Flights Within K Stops
- Medium Network Delay Time
- Hard Reconstruct Itinerary
Island
Traverse a matrix to find contiguous groups of elements.
- Easy Flood Fill
- Medium Max Area of Island
- Medium Number of Islands
Topological Sort
Sort nodes in a directed graph such that for every directed edge \((u, v)\) from vertex \(u\) to vertex \(v\), \(u\) comes before \(v\) in the ordering.
- Medium Alien Dictionary
- Medium Course Schedule
- Medium Minimum Height Trees
Data Structures: Hash Table
A hash table is a data structure that maps keys to values for highly efficient lookup. Usually implemented as an array of linked lists and a hashing function.
Complexity
Average Case
Search: O(1) Insert: O(1) Delete: O(1) Space: O(n)
Worst Case
Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Patterns
Key Problems
- Medium Find All Duplicates in an Array
- Easy Two Sum
- Easy Valid Anagram
Data Structures: Heap
Tree-based data structure that satisfies the heap property:
- In a max heap, the key of parent nodes is greater than or equal to the key of child nodes.
- In a min heap, the key of parent nodes is less than or equal to the key of child nodes.
class MinHeap:
def __init__(self):
self.heap = []
def push(self, element: int) -> None:
self.heap.append(element)
self._bubble_up(len(self.heap) - 1)
def pop(self) -> int:
if not self.heap:
return None
elif len(self.heap) == 1:
return self.heap.pop()
min_element = self.heap[0]
# Move the last element to the root and heapify down
self.heap[0] = self.heap.pop()
self._bubble_down(0)
return min_element
def peek(self) -> int:
min_element = self.heap[0]
return min_element
def _bubble_up(self, index: int) -> None:
while index > 0:
parent_index = (index - 1) // 2
if self.heap[index] < self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
index = parent_index
else:
break
def _bubble_down(self, index: int) -> None:
length = len(self.heap)
while True:
left_child = 2 * index + 1
right_child = 2 * index + 2
smallest = index
if left_child < length and self.heap[left_child] < self.heap[smallest]:
smallest = left_child
if right_child < length and self.heap[right_child] < self.heap[smallest]:
smallest = right_child
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
index = smallest
else:
break
Complexity
Average Case
Push: O(1) Pop: O(log n) Peek: O(1) Space: O(n)
Worst Case
Push: O(log n) Pop: O(log n) Peek: O(1) Space: O(n)
Patterns
\(k\)-way Merge
Merge \(k\) sorted lists.
- Medium Kth Smallest Element in a Sorted Matrix
- Hard Merge K Sorted Lists
- Hard Smallest Range Covering Elements from K Lists
Top-\(k\) Elements
Find the top-\(k\) elements in a certain category.
- Medium K Closest Points to Origin
- Easy Kth Largest Element in a Stream
- Medium Top K Frequent Elements
Two Heaps
To find the median, use two heaps: a min heap to find the smallest element in one part and a max heap to find the largest element in the other part.
- Hard Find Median from Data Stream
- Hard Sliding Window Median
- Hard IPO
Data Structures: Linked List
A data structure that represents a sequence of nodes, with each element pointing to the next.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val: int) -> None:
if not self.head:
self.head = ListNode(val)
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = ListNode(val)
def prepend(self, val: int) -> None:
new_head = ListNode(val)
new_head.next = self.head
self.head = new_head
def delete(self, val: int) -> None:
cur_node = self.head
if cur_node and cur_node.val == val:
# Delete from beginning
self.head = cur_node.next
cur_node = None
return
prev = None
while cur_node and cur_node.val != val:
prev = cur_node
cur_node = cur_node.next
if cur_node is None:
# Not found
return
prev.next = cur_node.next
cur_node = None
Complexity
Average Case
Append: O(n) Prepend: O(1) Delete: O(n) Space: O(n)
Worst Case
Append: O(n) Prepend: O(1) Delete: O(n) Space: O(n)
Patterns
Key Problems
- Easy Merge Two Sorted Lists
- Medium Remove Nth Node From End of List
- Medium LRU Cache
Fast & Slow Pointers
Two pointers move at different speeds in a linked list in order to detect cycles or find middle elements.
- Medium Find the Duplicate Number
- Easy Linked List Cycle
- Easy Palindrome Linked List
In-place Reversal of a Linked List
Reverse elements of a linked list in-place.
- Medium Reorder List
- Easy Reverse Linked List
- Hard Reverse Nodes in k-Group
Data Structures: Stack & Queue
Stack
Last in, first out data structure.
class Stack:
def __init__(self):
self.stack = []
def push(self, item: int) -> None:
self.stack.append(item)
def pop(self) -> int:
if self.is_empty():
print("Pop from empty stack")
return None
return self.stack.pop()
def peek(self) -> int:
if self.is_empty():
print("Peek from empty stack")
return None
return self.stack[-1]
def is_empty(self) -> bool:
return len(self.stack) == 0
Queue
First in, first out data structure.
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item: int) -> None:
self.queue.append(item)
def dequeue(self) -> int:
if self.is_empty():
print("Dequeue from empty queue")
return None
return self.queue.popleft()
def peek(self) -> int:
if self.is_empty():
print("Peek from empty queue")
return None
return self.queue[0]
def is_empty(self) -> bool:
return len(self.queue) == 0
Complexity
Average Case
Push: O(1) Pop: O(1) Peek: O(1) Space: O(n)
Worst Case
Push: O(1) Pop: O(1) Peek: O(1) Space: O(n)
Patterns
Key Problems
- Medium Evaluate Reverse Polish Notation
- Medium Min Stack
- Easy Valid Parentheses
Monotonic Stack
Use a stack to maintain a monotonic (either entirely non-increasing or non-decreasing) order of elements.
- Medium Daily Temperatures
- Hard Largest Rectangle in Histogram
- Easy Next Greater Element I
# Template
stack = []
for num in nums:
while stack and stack[-1] < num:
old_num = stack.pop()
# Do something with old_num
stack.append(num)
Data Structures: Trie
A tree data structure used to store and retrieve a set of strings.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
node = self.root
for c in word:
node = node.setdefault(c, {})
node['$'] = True # string terminal key
def search(self, word: str) -> bool:
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
return '$' in node
Complexity
Average Case
Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Worst Case
Search: O(n) Insert: O(n) Delete: O(n) Space: O(n)
Patterns
Key Problems
- Easy Longest Common Prefix
- Medium Word Break
- Hard Word Search II
Data Structures: Union-Find
Stores a collection of disjoint (non-overlapping) sets.
class UnionFind:
def __init__(self, size: int):
self.count = size
self.parent = list(range(size))
def find(self, x: int) -> int:
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x: int, y: int) -> None:
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
self.count -= 1
def connected(self, x: int, y: int) -> bool:
rootX = self.find(x)
rootY = self.find(y)
return rootX == rootY
Optimisation: Path Compression
Make every node between the query node and the root point to the root.
class UnionFind:
def __init__(self, size: int):
...
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> None:
...
def connected(self, x: int, y: int) -> bool:
...
Optimisation: Union-by-Rank
Ensure that when two trees are unioned, the shorter tree (lower rank) is attached under the root of the taller tree (higher rank) to keep the overall structure as flat as possible. The rank represents the approximate height of the tree.
class UnionFind:
def __init__(self, size: int):
...
self.rank = [0] * size
def find(self, x: int) -> int:
...
def union(self, x: int, y: int) -> None:
rootX = self.find(x)
rootY = self.find(y)
if rootX == rootY:
return
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
self.count -= 1
def connected(self, x: int, y: int) -> bool:
...
Complexity
Average Case
Search: O(α(n)) (amortized) Insert: O(1) Space: O(n)
Worst Case
Search: O(α(n)) (amortized) Insert: O(1) Space: O(n)
Patterns
Key Problems
- Medium Number of Connected Components in an Undirected Graph
- Medium Number of Provinces
- Medium Redundant Connection
Python
Simple statements.
global
Declare that a variable inside a nested function refers to a variable in the nearest enclosing scope that is not global.
nonlocal
Declare that a variable inside a function refers to a globally defined variable.
Python: collections
Container datatypes.
Counter
Dict subclass for counting hashable objects.
>>> Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]
defaultdict
Dict subclass that calls a factory function to supply missing values.
>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
... d[k].append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
deque
List-like container with fast appends and pops on either end. Implemented using a doubly-linked list. Supports appendleft
and popleft
.
Python: functools
Higher-order functions and operations on callable objects.
@functools.cache(user_function)
Simple lightweight unbounded function cache.
@functools.cache
def factorial(n: int) -> int:
return n * factorial(n-1) if n else 1
>>> factorial(10) # no previously cached result, makes 11 recursive calls
3628800
>>> factorial(5) # just looks up cached value result
120
>>> factorial(12) # makes two new recursive calls, the other 10 are cached
479001600
Python: heapq
Heap queue algorithm.
heappush(heap, item)
Push the value item onto the heap, maintaining the heap invariant.
heappop(heap)
Pop and return the smallest item from the heap, maintaining the heap invariant.
heapify(x)
Transform list x into a heap, in-place, in linear time.
nlargest(n, iterable, key=None)
Return a list with the n largest elements from the dataset defined by iterable.
nsmallest(n, iterable, key=None)
Return a list with the n smallest elements from the dataset defined by iterable.
Python: itertools
Functions creating iterators for efficient looping
combinations(iterable, r)
Return r length subsequences of elements from the input iterable.
islice(iterable, stop)
Make an iterator that returns selected elements from the iterable.
permutations(iterable, r=None)
Return successive r length permutations of elements from the iterable.
product(*iterables, repeat=1)
Cartesian product of input iterables.
zip_longest(*iterables, fillvalue=None)
Make an iterator that aggregates elements from each of the iterables. If the iterables are of uneven length, missing values are filled-in with fillvalue
.
Advanced Topics
Algorithms
Horner’s Method
Recursive algorithm for polynomial evaluation.
\[\begin{eqnarray} && a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n \\ &=& a_0 + x \Big(a_1 + x \big(a_2 + \cdots + x(a_{n-1} + x \, a_n) \cdots \big) \Big) \end{eqnarray}\]Boyer–Moore String-Searching Algorithm
Skips sections of the text by aligning the pattern from right to left and leveraging mismatches to jump over portions of the text, making it efficient for large alphabets.
Knuth-Morris-Pratt (KMP) String-Searching Algorithm
Avoids redundant comparisons by precomputing a partial match table (or “prefix” table) that allows the pattern to “jump” over mismatched characters, enabling efficient pattern searching in linear time.
Rabin–Karp String-Searching Algorithm
Finds a pattern by hashing the pattern and substrings of the text, allowing for quick comparisons and the ability to skip checking if the hash values do not match, making it especially useful for multiple pattern searches.
Manacher’s Longest Palindromic Substring Algorithm
Time: O(n)
Expand around possible centers while leveraging previously computed results to minimize redundant checks, achieving linear time complexity.
QuickSelect
Prefix Sum
Find a number of continuous subarrays/submatrices/tree paths that sum to target
Data Structures
- Fenwick Tree: Efficiently update values and calculate prefix sums in an array of values.
- Interval Tree: TODO
- Segment Tree with Lazy Propagation and Coordinate Compression: TODO
Theory
NP-Complete Problems
No polynomial-time algorithm is currently known to solve these problems optimally.
- Hamiltonian path problem
- Knapsack problem
- Subset sum problem
- Traveling salesman problem
- Vertex cover problem
Pick’s Theorem
Determine the area of a polygon with integer vertex coordinates when given the number of integer interior (\(i\)) and boundary (\(b\)) points: \(A = i + \frac{b}{2} - 1\).
Shoelace Formula
Determine the area of a polygon with integer points.