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 Solving¹

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(2ⁿ) O(n²) 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.²

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

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 multiply x by \(2^y\). x >> y is the same as //-ing x 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 Complement¹

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

Bitwise XOR

Use Bitwise XOR to solve problems.

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 Programming²¹

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

2-Dimensional

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

Algorithms: Sorting

Bubble Sort

Best: O(n) Average: O(n²) Worst: O(n²) 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(n²) Worst: O(n²) 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(n²) 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.²

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

Patterns³

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.

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.

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.

Medium Construct Binary Tree from Preorder and Inorder Traversal
Easy Path Sum
Medium Validate Binary Search Tree

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(V³) Average: O(V³) Worst: O(V³) Space: O(V²)

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

Island

Traverse a matrix to find contiguous groups of elements.

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.

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

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.

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.

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

Fast & Slow Pointers

Two pointers move at different speeds in a linked list in order to detect cycles or find middle elements.

In-place Reversal of a Linked List

Reverse elements of a linked list in-place.

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

Monotonic Stack

Use a stack to maintain a monotonic (either entirely non-increasing or non-decreasing) order of elements.

# 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

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.

Stirling’s Approximation for \(n!\)

\[\ln(n!) = n\ln n - n +O(\ln n)\]

LeetCode

Problem Solving1

Complexity

\(O\)-notation, \(\Omega\)-notation, \(\Theta\)-notation

Best Case, Worst Case, Average Case

Amortized Running Time

Recursive Running Time

Algorithms

Algorithms: Backtracking

Patterns

Key Problems

Subsets

Algorithms: Bit Manipulation

Bitwise Operators

NOT ~

AND &

OR |

XOR ^

Bit Shifts

Boolean Algebra

Two’s Complement1

Common Operations

Patterns

Key Problems

Bitwise XOR

Algorithms: Cascading

Algorithms: Dynamic Programming21

Steps for Solving Dynamic Programming Problems

Example: Fibonacci Sequence

Patterns

1-Dimensional

2-Dimensional

Algorithms: Greedy

Patterns

Key Problems

Algorithms: Sorting

Bubble Sort

Heapsort

Insertion Sort

Merge Sort

Quicksort

Data Structures

Data Structures: Array

Complexity

Average Case

Worst Case

Algorithms

Boyer-Moore Majority Vote Algorithm

Fisher-Yates Shuffle Algorithm

Kadane’s Maximum Subarray Algorithm

Rabin-Karp String Matching Algorithm

Patterns3

Binary Search

Intervals

Sliding Window

Two Pointers

Data Structures: Binary Search Tree

Algorithms

Pre-Order Traversal (Recursive)

Pre-Order Traversal (Iterative)

In-Order Traversal (Recursive)

In-Order Traversal (Iterative)

Post-Order Traversal (Recursive)

Post-Order Traversal (Iterative)

Complexity

Average Case

Worst Case

Patterns

Breadth-first Search

Depth-first Search

Data Structures: Graph

Minimum Spanning Tree

Algorithms

Bellman-Ford’s Single-Source Shortest Path Algorithm

Dijkstra’s Single-Source Shortest Path Algorithm

Floyd–Warshall’s All-Pairs Shortest Path Algorithm

Kahn’s Directed Acyclic Graph Topological Sort Algorithm

Kruskal’s Minimum Spanning Tree Algorithm

Prim’s Minimum Spanning Tree Algorithm

Hierholzer’s Eulerian Path Algorithm

Problem Solving¹

NOT `~`

AND `&`

OR `|`

XOR `^`

Two’s Complement¹

Algorithms: Dynamic Programming²¹

Patterns³

`global`

`nonlocal`

Python: `collections`

`Counter`

`defaultdict`

`deque`

Python: `functools`

`@functools.cache(user_function)`

Python: `heapq`

`heappush(heap, item)`

`heappop(heap)`

`heapify(x)`

`nlargest(n, iterable, key=None)`

`nsmallest(n, iterable, key=None)`

Python: `itertools`

`combinations(iterable, r)`

`islice(iterable, stop)`

`permutations(iterable, r=None)`

`product(*iterables, repeat=1)`