These are my distilled notes after grinding through a lot of problems. Not textbook theory -- just the things I keep going back to, plus the tricks that actually matter when the clock is ticking.

Linked Lists

Core properties

• Core advantage: add/remove at any position in O(1), but only if you already have a reference to the node before it (for singly linked lists)
• Core disadvantage: no random access -- you have to walk the list
• The goal is almost always elegant solutions with O(1) space -- no copying to arrays

The two-pointer pattern (most linked list problems reduce to this)

• Fast/slow pointers (Floyd's): fast moves 2 steps, slow moves 1 step
  • Find middle of list: when fast hits end, slow is at middle
  • Detect cycle: if fast and slow ever meet, there's a cycle
  • Find start of cycle: after they meet, reset one pointer to head -- they'll meet at the cycle start
• Two pointers n-apart: to find the n-th node from end, start second pointer n steps ahead, then walk both

# Find middle
slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow is now at middle

# Detect cycle
slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True  # cycle exists

In-place reversal

Reversal comes up constantly. The pattern is always three pointers:

prev, curr = None, head
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
return prev  # new head

Hacks

• Draw it out. Linked list bugs almost always come from losing a pointer. I sketch the before/after before touching the code.
• Dummy head node kills most edge cases at the head: dummy = ListNode(0); dummy.next = head
• "Do it in one pass" -- two pointers. "In-place" -- reversal.
• Palindrome linked list: find middle, reverse second half, compare both halves.
• Problems that look hard (reorder list, reverse in k-groups) almost always decompose into the same three primitives: find middle, reverse, merge.

Stacks

Core properties

• LIFO -- Last In, First Out
• Peek at top: stack[-1]
• Check length: len(stack)

Monotonic stacks

A monotonic stack maintains elements in strictly increasing or decreasing order. When you push, pop anything that violates the order first. This makes it powerful for "next greater/smaller element" problems.

# Next greater element for each item
stack = []  # stores indices
result = [-1] * len(nums)

for i, num in enumerate(nums):
    while stack and nums[stack[-1]] < num:
        idx = stack.pop()
        result[idx] = num  # current num is the "next greater" for idx
    stack.append(i)

Problems that scream "use a stack"

• Balanced parentheses / bracket matching: push opens, pop and verify on close
• Evaluate arithmetic expressions: two stacks (values + operators) or postfix conversion
• Largest rectangle in histogram: monotonic stack, classic O(n)
• Daily temperatures / stock span: next greater element variants
• Remove k digits / remove duplicates: greedy + monotonic stack
• Backspace string simulation (# deletes): simulate with a stack, never build the string upfront

Useful string checks that come up with stack problems

s.isalpha()   # True if all characters are English letters
s.isupper()   # True if all cased characters are uppercase
s.islower()   # True if all cased characters are lowercase
s.isdigit()   # True if all characters are digits

Hacks

• "Previous smaller element" -- monotonic stack, almost every time.
• Nested structures (HTML tags, math expressions, file paths) almost always reduce to a stack.
• "Greedy from the right" -- think stack.
• Iterative DFS is just a stack. When recursion gets too deep, I swap to an explicit stack.

Queues

Core properties

• FIFO -- First In, First Out
• Use collections.deque in Python for O(1) popleft

from collections import deque

queue = deque()
queue.append((x, y, z))     # enqueue
queue.popleft()              # dequeue

Gotcha with deque initialization: single items need wrapping:

deque([(x, y, z)])   # one tuple as starting element
deque([a, b, c])     # three separate elements

Monotonic deque (sliding window max/min)

The deque maintains a window of useful candidates in O(1) amortized per element. This is the trick behind the O(n) sliding window maximum problem.

# Sliding window maximum -- O(n)
from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, decreasing order of values
    result = []

    for i, num in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

BFS level-order trick

Instead of a nested loop for level tracking, use None as a delimiter:

queue = deque([root, None])

while queue:
    node = queue.popleft()
    if node is None:
        if queue:
            queue.append(None)  # mark end of next level
    else:
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

Hacks

• BFS = shortest path in unweighted graphs. Minimum steps, minimum jumps, minimum turns -- BFS first.
• I always pack extra state into the queue tuple: (node, level), (row, col, steps), (node, parent) -- keeps everything in one place.
• Multi-source BFS: seed the queue with all sources before the main loop, not one at a time.

Two Pointers and Sliding Window

These deserve their own section because they're everywhere.

Two pointers

Works when the array is sorted or when you're looking for pairs/triplets summing to a target.

# Two sum in sorted array
left, right = 0, len(arr) - 1
while left < right:
    s = arr[left] + arr[right]
    if s == target:
        return [left, right]
    elif s < target:
        left += 1
    else:
        right -= 1

• 3Sum: fix one pointer, two-sum on the rest. Sort first, skip duplicates.
• Container with most water: two pointers, always move the shorter side inward.
• Trapping rain water: either two pointers or precompute left-max and right-max arrays.

Sliding window

Use when you need an optimal subarray or substring satisfying some condition.

• Fixed size window: track sum/state as you slide, subtract left, add right
• Variable size window (expand/shrink): expand right, shrink left when constraint violated

# Longest substring without repeating characters
seen = {}
left = 0
best = 0

for right, ch in enumerate(s):
    if ch in seen and seen[ch] >= left:
        left = seen[ch] + 1
    seen[ch] = right
    best = max(best, right - left + 1)

Tip: if the window needs to track character frequency, use Counter or a defaultdict(int) and a variable tracking how many characters are "satisfied" -- this avoids scanning the whole window each step.

Binary Search

Binary search applies way beyond "find element in sorted array."

# Standard binary search
left, right = 0, len(nums) - 1
while left <= right:
    mid = left + (right - left) // 2  # avoids overflow vs (left+right)//2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

When to use binary search on the answer

If the problem says "find the minimum X such that condition(X) is true" -- binary search on X directly. The condition must be monotonic (once true, always true as X increases).

# Binary search on answer
left, right = min_possible, max_possible
while left < right:
    mid = (left + right) // 2
    if condition(mid):
        right = mid        # mid could be the answer, don't exclude it
    else:
        left = mid + 1

Classic examples: minimum speed to arrive on time, minimum capacity to ship packages, koko eating bananas.

bisect for sorted insertion

import bisect

bisect.bisect_left(arr, x)   # leftmost position to insert x
bisect.bisect_right(arr, x)  # rightmost position to insert x
bisect.insort(arr, x)        # insert x maintaining sorted order

Useful for: counting elements less than x, finding k-th smallest in a stream, insertion into sorted structure.

Trees

Traversal overview

• BFS: iterative, uses a queue, visits level by level
• DFS: recursive (uses the call stack) or iterative (explicit stack)
  • Pre-order: visit node, then left, then right
  • In-order: left, then visit node, then right
  • Post-order: left, then right, then visit node

Positional memory aid:

• Pre = before children
• In = between children
• Post = after children

In-order on a BST gives you elements in sorted order. That one property solves a huge class of problems.

Iterative DFS note

When pushing children onto a stack, push right first so left gets processed first. At any given step you're technically visiting the right subtree first (it sits lower on the stack), even though the traversal order ends up correct.

Space complexity: BFS vs DFS

Rule of thumb: DFS wins on wide trees, BFS wins on tall skinny trees.

Binary Search Tree (BST)

• Left value < node value < right value, all values unique
• Search, insert, delete: O(log n)
• Validate a BST: pass a (min_val, max_val) range down recursively -- every node must fall within its range
• In-order traversal yields sorted output -- use this to check if two BSTs have the same elements or find the k-th smallest

Common tree DFS patterns

Return multiple values from recursion. Many hard tree problems need you to compute two things at each node (e.g., height AND diameter candidate). Return a tuple.

def dfs(node):
    if not node:
        return 0, 0  # height, diameter

    lh, ld = dfs(node.left)
    rh, rd = dfs(node.right)

    height = 1 + max(lh, rh)
    diameter = max(ld, rd, lh + rh)  # path through this node
    return height, diameter

Path sum problems: carry a running sum downward. At a leaf, compare to target. For path-sum-from-any-node, use prefix sum + hashmap (same trick as subarray sum equals k).

Lowest Common Ancestor (LCA): if both targets are in different subtrees, current node is LCA. If both in same subtree, recurse down. Classic DFS.

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    return root if left and right else left or right

Initializing max/min variables

curr_max = float("-inf")
curr_min = float("inf")

Hacks

• "Compute something that depends on both children" -- post-order DFS.
• "Compute something that depends on ancestors" -- pre-order DFS, pass state downward.
• "Path not necessarily through root" -- DFS returning height upward while tracking a global max.
• Serialize/deserialize: pre-order with null markers. Deserialize with a queue.
• When I'm confused about which traversal to use, I trace a tiny example tree and ask what I actually need to know at each node.

Graphs

Core concepts

• Directed edges: one-way (arrows). Undirected edges: two-way (lines)
• Indegree: edges pointing in. Outdegree: edges pointing out
• Connected components: groups of mutually reachable nodes -- if two components exist, they're disjoint
• Graphs can be cyclic (contain a cycle) or acyclic -- binary trees are acyclic by definition
• DAG (Directed Acyclic Graph): the graph type that enables topological sort

Representing graphs

Adjacency list

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # for undirected

Adjacency matrix

# graph[i][j] == 1 means edge from i to j
graph[i][j] == 1

Matrix/grid as graph

The grid itself is the graph. Each cell is a node; neighbors are adjacent cells (4-directional or 8-directional). Standard directions array:

dirs = [(0,1),(0,-1),(1,0),(-1,0)]  # right, left, down, up

for dr, dc in dirs:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # valid neighbor

Graph traversal

Key difference from trees: trees have a root -- graphs don't always. I need a for loop over all nodes and a seen set.

seen = set()

def dfs(node):
    if node in seen:
        return
    seen.add(node)
    for neighbor in graph[node]:
        dfs(neighbor)

for node in range(n):
    if node not in seen:
        dfs(node)  # each call = one connected component

Time complexity: O(n + e) -- n nodes, e edges. Worst case fully connected: e = n^2.

Topological sort (for DAGs)

Two approaches:

Kahn's algorithm (BFS-based): start from all nodes with indegree 0, process them, decrement neighbors' indegrees, add any that hit 0.

from collections import deque

indegree = [0] * n
for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

queue = deque([i for i in range(n) if indegree[i] == 0])
order = []

while queue:
    node = queue.popleft()
    order.append(node)
    for nei in graph[node]:
        indegree[nei] -= 1
        if indegree[nei] == 0:
            queue.append(nei)

# If len(order) != n, there's a cycle

DFS-based: post-order DFS, prepend to result. Nodes with no outgoing edges finish first.

Topological sort comes up in: course schedule, build order, task dependencies, detecting cycles in directed graphs.

Cycle detection

• Undirected graph: DFS with parent tracking -- if you visit a node already in seen that isn't the parent, cycle exists
• Directed graph: DFS with a visiting state (gray/white/black coloring) -- if you hit a gray node, cycle exists

# Directed cycle detection
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n

def has_cycle(node):
    color[node] = GRAY
    for nei in graph[node]:
        if color[nei] == GRAY:
            return True  # back edge = cycle
        if color[nei] == WHITE and has_cycle(nei):
            return True
    color[node] = BLACK
    return False

Union-Find (Disjoint Set Union)

The go-to for "are these two nodes in the same connected component" queries, especially when edges are added incrementally.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Use Union-Find for: number of islands (offline), redundant connections, accounts merge, Kruskal's MST.

Dijkstra's shortest path

For weighted graphs where edge weights are non-negative. BFS is just Dijkstra with all weights = 1.

import heapq

def dijkstra(graph, src, n):
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]  # (distance, node)

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # stale entry
        for nei, weight in graph[node]:
            if dist[node] + weight < dist[nei]:
                dist[nei] = dist[node] + weight
                heapq.heappush(heap, (dist[nei], nei))
    return dist

Dijkstra comes up disguised as: network delay time, cheapest flight within k stops (modified), path with minimum effort.

BFS vs DFS on graphs

• DFS is usually cleaner to implement recursively
• BFS = shortest path in unweighted graphs -- visits nodes in order of distance from source
• Some problems need BFS specifically: word ladder (minimum transformations), 0-1 BFS, multi-source BFS

Multi-source BFS

When you need to spread from multiple starting points simultaneously (like rotting oranges spreading to adjacent fresh ones), seed the queue with all sources at once.

queue = deque()
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == source_value:
            queue.append((r, c, 0))  # (row, col, steps)

Hacks

• Counting connected components: DFS/BFS from each unvisited node, increment a counter each time -- each new DFS call is one component
• Bipartite check: BFS/DFS with 2-coloring -- if I ever need to give a node the same color as its neighbor, it's not bipartite (odd cycle)
• Island problems: DFS from each unvisited land cell, mark visited in-place to avoid recounting
• For back-edge detection in directed graphs -- gray/black coloring, not just a seen set
• Always check grid bounds before touching neighbors -- I always forget this and waste time debugging
• "Minimum cost path" with varying weights -- Dijkstra, not BFS

import sys
sys.setrecursionlimit(100000)  # for deep recursive DFS

Heaps

Core properties

• Heaps are the implementation behind priority queues
• A binary min-heap represents a complete binary tree stored as an array
• Root is always the minimum
• Node at index i: left child at 2i+1, right child at 2i+2
• Insert/remove: O(log n). Build from array: O(n) with heapify
• Repeated min/max extraction: goes from O(n^2) naive to O(n log n)

Python heap basics

Python only ships with a min-heap (heapq).

from heapq import heapify, heappush, heappop, nlargest, nsmallest

nums = [3, 1, 4, 1, 5]
heapify(nums)           # O(n) in-place
heappush(nums, 2)
smallest = heappop(nums)

# Top k elements without full sort
heapq.nlargest(k, nums)   # O(n log k)
heapq.nsmallest(k, nums)  # O(n log k)

Simulating a max-heap

Negate values on the way in, negate again on the way out:

stones = [-stone for stone in stones]
heapify(stones)

largest = abs(heappop(stones))

Heap with custom keys (tuples)

Python compares tuples lexicographically, so push (priority, item):

heappush(heap, (priority, item))
priority, item = heappop(heap)

For non-comparable items (like TreeNode objects), add a tie-breaking counter:

import itertools
counter = itertools.count()
heappush(heap, (priority, next(counter), item))

Classic heap patterns

K-th largest element: maintain a min-heap of size k. Every time heap grows past k, pop. The root is the k-th largest.

import heapq

def kth_largest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Merge K sorted lists: push the first element from each list into a min-heap, then greedily pop and advance.

heap = []
for i, lst in enumerate(lists):
    if lst:
        heappush(heap, (lst[0], i, 0))  # (val, list_idx, element_idx)

while heap:
    val, i, j = heappop(heap)
    # add val to result
    if j + 1 < len(lists[i]):
        heappush(heap, (lists[i][j+1], i, j+1))

Running median (two heaps pattern): maintain a max-heap for the lower half and a min-heap for the upper half. Keep them balanced. Median is always the top of one or the average of both tops.

lower = []  # max-heap (negate values)
upper = []  # min-heap

def add_num(num):
    heappush(lower, -num)
    # balance: largest of lower must be <= smallest of upper
    heappush(upper, -heappop(lower))
    if len(upper) > len(lower):
        heappush(lower, -heappop(upper))

def find_median():
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2

Hacks

• "k-th largest/smallest," "top k elements," "k closest points" -- heap.
• "Median of a stream" or "balance between two halves" -- two heaps.
• "Schedule tasks," "CPU scheduling," "task cooldown" -- heap + greedy.
• Heap is usually the bridge between a brute-force O(n^2) and something actually acceptable.
• "k closest points to origin" -- push (distance, point) tuples, keep a min-heap of size k.

Dynamic Programming

I won't cover every DP pattern here, but a few mental models that help me spot DP problems fast.

When to use DP

• The problem asks for a count, maximum, minimum, or boolean over all ways to do something
• You can define the problem recursively AND subproblems overlap
• Greedy doesn't work because local optimum doesn't guarantee global optimum

Top-down (memoization) vs bottom-up (tabulation)

• Top-down: write the recursive solution first, add a cache. Easier to reason about.
• Bottom-up: fill a table iteratively. Usually faster in practice (no recursion overhead).

# Top-down with cache
from functools import lru_cache

@lru_cache(maxsize=None)
def dp(i, remaining):
    if base_case:
        return ...
    return max(dp(i+1, ...), dp(i+1, ...))

Common DP patterns

• 0/1 Knapsack: include or exclude each item -- dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
• Unbounded knapsack: can reuse items -- inner loop doesn't reset
• Longest common subsequence (LCS): dp[i][j] = LCS of first i chars and first j chars
• Coin change: min coins to make amount -- classic unbounded knapsack
• Subarray/substring problems: often dp[i] = answer ending at index i

Space optimization trick

Many 2D DP tables only look at the previous row. You can reduce from O(n*m) to O(m) by keeping only one row and updating in place (sometimes reversed).

Python Utilities and Tricks

Collections

from collections import Counter, defaultdict, deque

# Counter: frequency map
freq = Counter("hello")   # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})
freq.most_common(2)       # top 2 most common

# defaultdict: no KeyError on missing keys
graph = defaultdict(list)
count = defaultdict(int)

# deque: O(1) append and popleft
q = deque()
q.append(x)
q.appendleft(x)
q.popleft()

Sorting tricks

# Sort by custom key
intervals.sort(key=lambda x: x[0])          # sort by start
points.sort(key=lambda p: p[0]**2 + p[1]**2)  # sort by distance

# Sort descending
nums.sort(reverse=True)

# Multiple sort keys
data.sort(key=lambda x: (x[0], -x[1]))  # asc first, desc second

Useful builtins

# divmod: quotient and remainder at once
divmod(17, 5)   # (3, 2)

# square root
n ** 0.5
int(n ** 0.5)   # integer square root (beware float precision for large n)

# integer square root (exact, no float issues)
import math
math.isqrt(n)

# all keys / first key
list(graph.keys())
next(iter(graph))

# enumerate: index + value
for i, val in enumerate(arr):
    ...

# zip: parallel iteration
for a, b in zip(list1, list2):
    ...

# zip to create pairs / transpose
pairs = list(zip(keys, values))
transposed = list(zip(*matrix))  # transpose a 2D matrix

# any / all
any(x > 0 for x in nums)
all(x > 0 for x in nums)

# accumulate prefix sums
from itertools import accumulate
prefix = list(accumulate(nums))          # [1, 3, 6, 10, ...]
prefix = list(accumulate(nums, max))     # running max

Suppress newline in print

print("hello", end="")

Math shortcuts

# Absolute value
abs(-5)       # 5

# Min/max with default
min(a, b, c)
max(arr)

# Infinity
float("inf")
float("-inf")

# Modular arithmetic (stays positive in Python even with negatives)
(-7) % 3   # 2 in Python (not -1 like in some other languages)

Patterns Worth Remembering

A cheat sheet of patterns and the problems they map to:

Meta hacks

• Constraints tell you the complexity target. n = 10 -- brute force fine. n = 10^5 -- need O(n log n) or better. n = 10^9 -- O(log n) or pure math.
• I always think through the brute force first, even when I know the optimal. It anchors the solution and makes the optimization obvious.
• Name the pattern before writing a line. "This is a sliding window" -- then code it. Naming it first stops me from wandering.
• When stuck: can I sort the input? Can I use a hashmap? Have I seen this structure before?
• Off-by-one errors kill more solutions than wrong algorithms. I always trace a tiny example through my loop bounds before moving on.
• left + (right - left) // 2 instead of (left + right) // 2 for binary search -- same in Python, but a habit worth keeping.