When

• Sorted array with target sum/diff.
• Palindrome / reverse / partition in place.
• Merge two sorted sequences.
• Squared sorted array, dutch flag, remove duplicates.

Template

# opposing ends
def two_sum_sorted(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target: return [l, r]
        if s < target: l += 1
        else: r -= 1
    return []

# same direction (partition / dedup)
def remove_duplicates(a):
    w = 0
    for r in range(len(a)):
        if r == 0 or a[r] != a[r-1]:
            a[w] = a[r]; w += 1
    return w

Fixed-Size

def max_sum_k(a, k):
    s = sum(a[:k]); best = s
    for i in range(k, len(a)):
        s += a[i] - a[i-k]
        best = max(best, s)
    return best

Variable

# longest substring with at most K distinct chars
def longest_k_distinct(s, k):
    cnt = {}; l = 0; best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        while len(cnt) > k:
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0: del cnt[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Floyd's Tortoise & Hare

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow is fast: break
    else: return None
    slow = head
    while slow is not fast:
        slow = slow.next; fast = fast.next
    return slow

Prefix Sum

p = [0] * (len(a) + 1)
for i, v in enumerate(a): p[i+1] = p[i] + v
# range sum [l, r] = p[r+1] - p[l]

# subarray sum equals K (count)
def count_k(a, k):
    seen = {0: 1}; s = 0; ans = 0
    for v in a:
        s += v
        ans += seen.get(s - k, 0)
        seen[s] = seen.get(s, 0) + 1
    return ans

Difference Array (range update)

# add v to a[l..r] in O(1); reconstruct in O(n)
d = [0] * (n + 1)
def update(l, r, v):
    d[l] += v; d[r+1] -= v
def build():
    a = [0] * n; cur = 0
    for i in range(n):
        cur += d[i]; a[i] = cur
    return a

Classic

def lower_bound(a, x):
    l, r = 0, len(a)
    while l < r:
        m = (l + r) // 2
        if a[m] < x: l = m + 1
        else: r = m
    return l   # first index with a[i] >= x

Binary Search on Answer

# minimum capacity to ship within D days
def feasible(cap, weights, D):
    days, cur = 1, 0
    for w in weights:
        if cur + w > cap: days += 1; cur = 0
        cur += w
    return days <= D

def min_capacity(weights, D):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        m = (lo + hi) // 2
        if feasible(m, weights, D): hi = m
        else: lo = m + 1
    return lo

BFS

from collections import deque
def bfs(start, adj):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

DFS

def dfs(u, adj, seen):
    seen.add(u)
    for v in adj[u]:
        if v not in seen: dfs(v, adj, seen)

# iterative
def dfs_iter(start, adj):
    stack = [start]; seen = {start}
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v not in seen:
                seen.add(v); stack.append(v)

Grid Walk

DIR = [(1,0),(-1,0),(0,1),(0,-1)]
def in_bounds(r, c, R, C): return 0 <= r < R and 0 <= c < C
# multi-source BFS for nearest-X distance, etc.

Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:]); return
    for c in choices:
        if not feasible(path, c): continue
        path.append(c)
        backtrack(path, next_choices(choices, c))
        path.pop()

Subsets / Permutations

def subsets(nums):
    out = []; cur = []
    def go(i):
        if i == len(nums): out.append(cur[:]); return
        go(i + 1)
        cur.append(nums[i]); go(i + 1); cur.pop()
    go(0); return out

Kahn's BFS

from collections import deque
def topo(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # [] = cycle

Template

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path compression
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

1D DP — House Robber

def rob(a):
    take = skip = 0
    for v in a:
        take, skip = skip + v, max(take, skip)
    return max(take, skip)

0/1 Knapsack

def knap(W, wt, val):
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

LIS

from bisect import bisect_left
def lis(a):
    tails = []
    for x in a:
        i = bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

Edit Distance

def edit(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

Interval DP

Burst balloons, matrix chain, palindrome partition. Iterate by length: for L in 2..n: for i in 0..n-L.

Bitmask DP

State = subset of n elements (n ≤ 20). TSP, assignments. dp[mask][i] = best ending at i covering mask.

Interval Scheduling

# max non-overlapping: sort by END
def max_intervals(iv):
    iv.sort(key=lambda x: x[1])
    end = -float('inf'); cnt = 0
    for s, e in iv:
        if s >= end: cnt += 1; end = e
    return cnt

# merge overlapping: sort by START
def merge(iv):
    iv.sort(); out = []
    for s, e in iv:
        if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
        else: out.append([s, e])
    return out

Heap Greedy

Meeting rooms II, k closest, merge k sorted, dijkstra. Pattern: pop min, push derived.

Next Greater Element

def next_greater(a):
    n = len(a); res = [-1] * n; st = []
    for i in range(n):
        while st and a[st[-1]] < a[i]:
            res[st.pop()] = a[i]
        st.append(i)
    return res

Sliding Window Max

from collections import deque
def max_window(a, k):
    dq = deque(); out = []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: out.append(a[dq[0]])
    return out

Common Tricks

x & (x - 1)         # clear lowest set bit
x & -x              # isolate lowest set bit
bin(x).count('1')   # popcount
x ^ y               # set of differing bits

# single number (others appear twice)
def single(a):
    r = 0
    for v in a: r ^= v
    return r

# subset enumeration of bitmask m
sub = m
while sub:
    process(sub)
    sub = (sub - 1) & m

Trie: Prefix Tree for Fast String Lookup

A trie stores strings by sharing common prefixes along tree edges. Each node holds up to 26 children (lowercase alphabet) plus an isEnd flag. Insert and search cost O(L) where L is word length — independent of how many words are stored — which is why tries beat hash sets for prefix queries and autocomplete.

• When to use — prefix search, autocomplete, longest-common-prefix, word-break dictionaries, IP routing (bit tries), and XOR-max problems (binary trie).
• Space cost — up to O(N × L × 26) pointers worst case; use a hash-map of children when the alphabet is large or sparse.

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):     # O(L)
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):     # O(L) exact match
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):   # O(L) prefix exists
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

    def autocomplete(self, prefix, limit=10):
        node, out = self._walk(prefix), []
        if not node: return out
        stack = [(node, prefix)]
        while stack and len(out) < limit:
            cur, path = stack.pop()
            if cur.is_end: out.append(path)
            for c, nxt in sorted(cur.children.items(), reverse=True):
                stack.append((nxt, path + c))
        return out

String Matching: KMP Failure Function & Rabin-Karp Rolling Hash

Naive substring search is O(N×M). KMP precomputes a failure (LPS = longest proper prefix that is also suffix) array so the text pointer never backtracks, giving O(N+M). Rabin-Karp hashes each window in O(1) via a rolling polynomial hash, matching in O(N+M) average but O(N×M) worst case on hash collisions.

# KMP — build LPS then scan, O(N+M)
def build_lps(p):
    lps = [0] * len(p)
    k = 0                       # length of current prefix-suffix
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = lps[k - 1]      # fall back, no text rescan
        if p[i] == p[k]:
            k += 1
        lps[i] = k
    return lps

def kmp(text, p):
    lps, k, hits = build_lps(p), 0, []
    for i, ch in enumerate(text):
        while k and ch != p[k]:
            k = lps[k - 1]
        if ch == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - k + 1)
            k = lps[k - 1]
    return hits

# Rabin-Karp — rolling hash, O(N+M) average
def rabin_karp(text, p, base=256, mod=(1<<61)-1):
    n, m = len(text), len(p)
    if m > n: return []
    high = pow(base, m - 1, mod)
    ph = th = 0
    for i in range(m):          # hash pattern + first window
        ph = (ph * base + ord(p[i])) % mod
        th = (th * base + ord(text[i])) % mod
    hits = []
    for i in range(n - m + 1):
        if ph == th and text[i:i+m] == p:   # verify to kill collisions
            hits.append(i)
        if i < n - m:            # roll: drop left char, add right
            th = ((th - ord(text[i]) * high) * base + ord(text[i+m])) % mod
    return hits

Weighted Shortest Paths: Dijkstra, Bellman-Ford, A*

Pick by edge weights and heuristic availability. Dijkstra is the default for non-negative weights; Bellman-Ford handles negatives and detects negative cycles; A* speeds Dijkstra with an admissible heuristic for point-to-point queries on grids/maps.

import heapq
# Dijkstra — non-negative weights, O((V+E) log V)
def dijkstra(graph, src):        # graph: u -> [(v, w)]
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue             # stale entry — skip
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

# Bellman-Ford — handles negatives, detects neg cycle, O(V*E)
def bellman_ford(edges, n, src): # edges: [(u, v, w)]
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):       # relax V-1 times
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:        # extra pass = cycle check
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist

# A* — Dijkstra + heuristic h(n) toward goal
def a_star(graph, src, goal, h):
    g = {src: 0}
    pq = [(h(src), 0, src)]      # (f=g+h, g, node)
    while pq:
        _, gu, u = heapq.heappop(pq)
        if u == goal: return gu
        if gu > g.get(u, float('inf')): continue
        for v, w in graph[u]:
            ng = gu + w
            if ng < g.get(v, float('inf')):
                g[v] = ng
                heapq.heappush(pq, (ng + h(v), ng, v))
    return float('inf')

Minimum Spanning Tree: Kruskal + Union-Find and Prim

An MST connects all V vertices with V−1 edges of minimum total weight. Kruskal sorts edges and greedily adds the cheapest that does not form a cycle, using union-find (disjoint set) to test connectivity in near-O(1). Prim grows one tree from a seed, always pulling the cheapest crossing edge via a heap.

# Union-Find with path compression + union by rank
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path halving
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False           # already connected -> cycle
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

def kruskal(n, edges):           # edges: [(w, u, v)], O(E log E)
    dsu, mst, cost = DSU(n), [], 0
    for w, u, v in sorted(edges):
        if dsu.union(u, v):
            mst.append((u, v, w))
            cost += w
    return cost, mst

import heapq
def prim(graph, start=0):        # graph: u -> [(w, v)], O(E log V)
    seen, pq, cost = {start}, list(graph[start]), 0
    heapq.heapify(pq)
    while pq and len(seen) < len(graph):
        w, v = heapq.heappop(pq)
        if v in seen: continue
        seen.add(v); cost += w
        for w2, nxt in graph[v]:
            if nxt not in seen:
                heapq.heappush(pq, (w2, nxt))
    return cost

Binary Search Trees: Insert, Delete, Validate, Iterative Traversals

A BST keeps left < node < right, giving O(h) search/insert/delete where h is height (O(log n) balanced, O(n) degenerate). Validation must carry min/max bounds down the tree — checking only immediate children is a classic wrong answer. Iterative traversals use an explicit stack to avoid recursion-depth limits.

def insert(root, val):
    if not root: return Node(val)
    if val < root.val: root.left = insert(root.left, val)
    else:             root.right = insert(root.right, val)
    return root

def delete(root, key):
    if not root: return None
    if key < root.val:  root.left = delete(root.left, key)
    elif key > root.val: root.right = delete(root.right, key)
    else:                               # found
        if not root.left:  return root.right
        if not root.right: return root.left
        succ = root.right               # in-order successor
        while succ.left: succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if not (lo < root.val < hi): return False
    return (is_valid_bst(root.left,  lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

def inorder_iter(root):          # left, node, right -> sorted for BST
    st, cur, out = [], root, []
    while cur or st:
        while cur:
            st.append(cur); cur = cur.left
        cur = st.pop(); out.append(cur.val)
        cur = cur.right
    return out

def preorder_iter(root):
    st, out = ([root] if root else []), []
    while st:
        n = st.pop(); out.append(n.val)
        if n.right: st.append(n.right)   # push right first
        if n.left:  st.append(n.left)
    return out

def postorder_iter(root):        # reverse of modified preorder
    st, out = ([root] if root else []), []
    while st:
        n = st.pop(); out.append(n.val)
        if n.left:  st.append(n.left)
        if n.right: st.append(n.right)
    return out[::-1]

Tree Patterns: LCA, DP-on-Trees, Serialize / Deserialize

Beyond BSTs, three patterns dominate tree interviews. LCA finds the deepest node that is an ancestor of two targets. DP-on-trees does a single post-order pass returning per-subtree state (the "rob the house" and diameter problems). Serialize/deserialize encodes structure to a string and rebuilds it — pre-order with null markers is the cleanest.

# LCA in a binary tree — O(n), returns lowest common ancestor
def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    L = lca(root.left, p, q)
    R = lca(root.right, p, q)
    if L and R: return root      # p, q split -> this is the LCA
    return L or R

# DP on tree — max path sum through any node, O(n)
def max_path_sum(root):
    best = float('-inf')
    def gain(node):              # max downward gain from node
        nonlocal best
        if not node: return 0
        l = max(gain(node.left), 0)   # drop negative branches
        r = max(gain(node.right), 0)
        best = max(best, node.val + l + r)   # split at node
        return node.val + max(l, r)           # extend one side
    gain(root)
    return best

# Serialize / deserialize — pre-order with '#' for null
def serialize(root):
    out = []
    def dfs(n):
        if not n: out.append('#'); return
        out.append(str(n.val)); dfs(n.left); dfs(n.right)
    dfs(root)
    return ','.join(out)

def deserialize(data):
    vals = iter(data.split(','))
    def build():
        v = next(vals)
        if v == '#': return None
        n = Node(int(v))
        n.left = build(); n.right = build()
        return n
    return build()

Range Queries: Segment Tree with Lazy Propagation & Fenwick / BIT

When you need range aggregates plus updates, arrays give O(1) query but O(n) update; prefix sums give O(1) query but O(n) update. Fenwick (Binary Indexed Tree) does point-update + prefix-query in O(log n) with tiny constants. A segment tree generalizes to any associative operation; lazy propagation defers range updates so both range-update and range-query stay O(log n).

# Fenwick / BIT — point update, prefix sum, O(log n)
class BIT:
    def __init__(self, n):
        self.t = [0] * (n + 1)
    def update(self, i, delta):      # 1-indexed
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)            # jump to next responsible node
    def query(self, i):              # sum of [1..i]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.query(r) - self.query(l - 1)

# Segment tree with lazy propagation — range add + range sum
class LazySeg:
    def __init__(self, arr):
        self.n = len(arr)
        self.t = [0] * (4 * self.n)
        self.lz = [0] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)
    def _build(self, a, node, lo, hi):
        if lo == hi: self.t[node] = a[lo]; return
        mid = (lo + hi) // 2
        self._build(a, 2*node, lo, mid)
        self._build(a, 2*node+1, mid+1, hi)
        self.t[node] = self.t[2*node] + self.t[2*node+1]
    def _push(self, node, lo, hi):
        if self.lz[node]:
            mid = (lo + hi) // 2
            for ch, l, h in ((2*node, lo, mid), (2*node+1, mid+1, hi)):
                self.t[ch] += self.lz[node] * (h - l + 1)
                self.lz[ch] += self.lz[node]
            self.lz[node] = 0
    def update(self, ql, qr, val, node=1, lo=0, hi=None):
        if hi is None: hi = self.n - 1
        if qr < lo or hi < ql: return
        if ql <= lo and hi <= qr:         # full cover -> defer
            self.t[node] += val * (hi - lo + 1)
            self.lz[node] += val
            return
        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        self.update(ql, qr, val, 2*node, lo, mid)
        self.update(ql, qr, val, 2*node+1, mid+1, hi)
        self.t[node] = self.t[2*node] + self.t[2*node+1]
    def query(self, ql, qr, node=1, lo=0, hi=None):
        if hi is None: hi = self.n - 1
        if qr < lo or hi < ql: return 0
        if ql <= lo and hi <= qr: return self.t[node]
        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        return (self.query(ql, qr, 2*node, lo, mid) +
                self.query(ql, qr, 2*node+1, mid+1, hi))

Linked-List Manipulation: Reverse, Cycle Detection, Merge k Lists

Linked-list problems reward pointer discipline: a dummy head simplifies edge cases, and Floyd's tortoise-and-hare finds cycles in O(1) space. Reversal is the atomic skill (reverse whole list, reverse in k-groups, palindrome check). Merging k sorted lists uses a min-heap for O(N log k).

def reverse(head):               # iterative, O(n) time, O(1) space
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev          # flip pointer
        prev, cur = cur, nxt
    return prev                  # new head

def has_cycle(head):             # Floyd's — O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def cycle_start(head):           # find node where cycle begins
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:         # meet inside cycle
            p = head
            while p is not slow: # advance both 1 step -> entry
                p, slow = p.next, slow.next
            return p
    return None

import heapq
def merge_k(lists):              # O(N log k)
    heap = [(n.val, i, n) for i, n in enumerate(lists) if n]
    heapq.heapify(heap)
    dummy = tail = Node(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node; tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next