Data Structures & Algorithms Cheat Sheet

# drop constants and lower terms
# 3n² + 100n + 5  →  O(n²)
O(1) < O(log n) < O(n) < O(n log n)
       < O(n²) < O(2ⁿ) < O(n!)

for x in a:          # O(n)  consecutive: add
    ...
for x in a:
    for y in a:      # O(n²) nested: multiply
        ...

# linear search of n items
# best  O(1)  hit at the front
# worst O(n)  missing, or at the end
# space O(1)  a handful of variables

a = [4, 1, 7]
a[0]            # O(1) by index
a.append(9)     # O(1) amortized at the end
# insert or delete at the front: O(n)

s = "level"
s[0], s[-1]           # ends
s == s[::-1]          # palindrome check
# anagram: sorted(s) == sorted(t)

# sorted array, or a palindrome
i, j = 0, len(a) - 1
# move the side that is still wrong
# pair-sum, partition, reverse in place

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt   # the arrow
# 1 -> 2 -> 3 -> None

node = head
while node:            # O(n) to reach i
    node = node.next
# insert at the head is O(1)
# no random access

# doubly: node.prev and node.next
# circular: tail.next is head
# cycle? slow and fast pointers
# if they meet, a loop exists

stack = []
stack.append(x)    # push
stack.pop()        # pop the top
# undo, recursion, balanced brackets

pair = {")": "(", "]": "[", "}": "{"}
# open: push it
# close: pop, and it must match
# valid if the stack ends empty

from collections import deque
q = deque()
q.append(x)      # enqueue at the back
q.popleft()      # dequeue the front
# deque: both ends; heap: priority

def fact(n):
    if n == 0:              # base: stop
        return 1
    return n * fact(n - 1)  # smaller n

# do not simulate every frame at once
# assume fact(n - 1) is already right
# then attach the work for n
# missing base case → RecursionError

# move n-1 aside, move the disk,
# move n-1 on top
# 1 disk = 1 move
# n disks = 2ⁿ - 1

# bubble, selection, insertion  O(n²)
# merge, heap               O(n log n)
# quick average O(n log n), worst O(n²)
# merge is stable; quick usually is not

# split until one item (already sorted)
# merge two sorted halves:
# take the smaller head each time
# counting sort is O(n + k), not comparison

# unsorted: look at every item, O(n)
# sorted: throw away half, O(log n)
lo, hi = 0, len(a) - 1
mid = (lo + hi) // 2

# a must be sorted
# target < a[mid] → hi = mid - 1
# target > a[mid] → lo = mid + 1
# equal → found; lo > hi → absent

class T:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
# pre: node, left, right
# in:  left, node, right
# post: left, right, node

# every left value  < node
# every right value > node
# search / insert is O(h)
# balanced h ≈ log n; skewed h = n

# parent of i:     (i - 1) // 2
# children of i:   2*i+1, 2*i+2
# max-heap: parent >= children
# peek min or max in O(1)

# a queue, not the call stack
# push the root, then its children
# each pop is the next level-left node
# heap sort: build a heap, pop n times

seen = {}
seen["ada"] = 1
"ada" in seen     # hash, then the bucket
# worst case O(n) if everything collides

# index = hash(key) % buckets
# chaining: a list in that bucket
# open addressing: probe the next slot
# load factor high → more collisions

# same key → same bucket, always
# spread keys; don't use only one field
# mutable keys break the bucket
# Python dicts and sets are hash tables

g = {"A": ["B", "C"], "B": ["C"], "C": []}
# list: sparse, O(V + E) to scan
# matrix: g[u][v] is 1 if an edge, O(V²)
# directed or not; weighted or not

# BFS: queue, layer by layer
# shortest path when every edge is 1
# DFS: stack or recursion, go deep
# mark visited or you loop forever

# Dijkstra: non-negative weights, best path
# a negative edge → Bellman-Ford
# topo sort: directed, no cycles
# an edge u→v means u comes first

# overlapping subproblems + optimal pieces
memo = {}
def fib(n):
    if n < 2: return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
# tabulation: fill a table from the base

# activity selection:
# sort by finish time
# take the next one that starts after
# the last finish you took
# only correct when a local best stays best

def bt(path):
    if done(path):
        save(path); return
    for choice in options:
        path.append(choice)  # choose
        bt(path)             # explore
        path.pop()           # undo