01

Dynamic Arrays

The standard list in Python is a dynamic array. It supports the operations:

The big things to note are:

  1. lst.pop(0) is O(n) since you're left-shifting all the elements to right.
    • lst = [x] creates a shallow copy of the list.
  2. lst.pop() removes the rightmost element in O(1) time.
  3. x in lst is an O(n) operation that does a linear scan.
  4. lst[:] returns a shallow copy of lst.
  5. lst.sort() sorts in-place and lst.reverse() reverses in-place.
    • sorted(lst) returns a sorted copy; reversed(lst) is the reversal analogue.
  6. lst[i] accesses element i and lst[i] = x sets it.
    • accessing a slice of a list is done by writing lst[start:end:step]; end is an exclusive bound.
02

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']
  • str is immutable; s[:] produces a copy of s^{converting str into array of chars and joining back avoids copy costs}
03

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)
04

STL

  • bisect.bisect(arr, target) is an alias for bisect.right(arr, target)
  • bisect.bisect_left(arr, target) yields the leftmost instance of target or the insertion point
  • bisect.insort_right (bisect.insort) and bisect.insort_left perform an O(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.

  1. 3-way partition:
    • l<=r for (values < target, values == target, values > target)
  2. 2-way partition
    • l<r for (values<target, values>=target)
    • r-l>1 for 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
05

Sets & Maps

06

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 mergeddef 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 randomdef 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 randomdef 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, gtdef 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 randomdef 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)
07

Stacks & Queues

Stack: FIFO Queue: LIFO

08

Recursion

09

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
10

Trees

from typing import Optionalclass BinaryNode:    def __init__(self, val, left: Optional['BinaryNode'], right: Optional['BinaryNode']):        self.val = val        self.left = left        self.right = rightclass 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 Optionaldef 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 dequedef 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
11

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 = valuefrom collections import defaultdictdef 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 $V$ vertices, we consume $V^2$ 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 defaultdictdef 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 defaultdictdef 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 defaultdictdef 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 dequedef 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 heapqdef 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
12

Grids

  • Do NOT write [[0] * num_cols] * num_rows.
    • Instead: [[0] * num_cols for _ in range(num_rows)]
  • 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 dequedef 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
13

Matrices

14

Heaps

Heaps: Neither LIFO nor FIFO. They enable access to the next element in order of priority.

Array-Based Heap

import heqpqarray = [2,1,6,7,8,1,3,4,5]heapq.heapify(array)heapq.heappop(array) # removes and returns array minheapq.heappush(array, 9) # adds 9 to the heapheapq.heappushpop(array, 9) # pushes then popheapq.heapreplace(array, 9) # pop then pushdef 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) // 2def left_child(idx):    return 2*idx + 1def right_child(idx):    return 2*idx + 2class 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)
15

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
16

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 respermutations_without_repetition([0,1,2,3])
17

Dynamic Programming

18

Greedy Algorithms

19

Topological Sort

A DAG, a directed acyclic graph, is a directed graph without cycles. DAG ⇔ Topologically Sortable.

DAG Problem Types:

  1. Is this a DAG?
    • Try to top-sort it (via Kahn's Algorithm). 1[1]DFS can also be used, but it's finicky.
  2. top-sort an edge list.
  3. Find shortest / longest path in DAG (even with negative weights).
  4. How many topological orderings are there?
    • At each order nodes step while top-sorting via Kahn's, count the number of options.
      • Then it's a counting problem, i.e. you have n nodes in zeros, so n! ways of ordering those zero in-degrees. In the next iteration, if you m nodes in zeros, that would mean m! orderings of that level. So a total of n!*m! orders of these two levels.

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 orderingdef 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))]
20

Prefix Sums

21

Monotonic Stacks & Queues

22

Set & Map Implementations

23

Advanced Dynamic Programming

24

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_yclass 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 rootclass 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_xclass 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
25

Tries

26

Bit Manipulation

27

Data Structures Design

28

Advanced Graphs

29

Math

1DFS can also be used, but it's finicky.