Techniques

Each section is a technique the Patterns table points to — the how behind the what.

Two pointers

Walk two indices instead of a nested loop — turns many O(n²) scans into O(n). Four shapes:

Sliding window

Substring/subarray with a constraint, in O(n): expand right to include elements; when the window violates the constraint, shrink from left. Track window state (a count, Counter, or sum) incrementally — don't rebuild it. Fixed-size: slide both ends together. LC 643, 1456, 1004, 1493. For a sliding time window over a stream, use a deque (append new, popleft expired). LC 933.

Prefix sum

prefix[i] = a scalar aggregate (sum/product/max/XOR) over input[:i] — NOT a sub-array. Range sum [i, j) = prefix[j] - prefix[i] in O(1) after O(n) build. Pair with a hash map for "subarray summing to K" (store seen prefix sums, look for prefix - K). Range updates → Fenwick/BIT. LC 238.

Binary search templates

Canonical "find exact value" — three-way branch, closed interval [lo, hi].

def binary_search(target, lo, hi):
    while lo <= hi:                    # `<=` so lo == hi gets checked
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid                 # early-exit on hit
        elif arr[mid] < target:
            lo = mid + 1               # answer is to the right
        else:
            hi = mid - 1               # answer is to the left
    return -1                          # not found

Bisect-left / "find leftmost insertion point" — predicate-based, half-open interval [lo, hi). Generalizes to "find leftmost index where some monotonic predicate is True."

def bisect_left(target, arr):
    lo, hi = 0, len(arr)               # hi = len, exclusive
    while lo < hi:                     # `<`, not `<=`
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1               # answer is strictly to the right
        else:
            hi = mid                   # mid might still be the answer — keep in range
    return lo                          # lo == hi at exit

Three key shifts from canonical: half-open interval (hi = len), lo < hi, hi = mid (not mid - 1), no early return.

# Python stdlib — use these when allowed; hand-roll when asked
import bisect
bisect.bisect_left(arr, x)             # leftmost insertion point (arr[i] >= x)
bisect.bisect_right(arr, x)            # rightmost insertion point (arr[i] > x)
bisect.insort_left(arr, x)             # actually insert, maintain sort (mutates)
# left vs right matters on duplicates:
# arr=[1,3,5,5,5,7]; bisect_left(arr,5)=2, bisect_right(arr,5)=5

Predicate-based template generalization: when check(mid) returns True/False and is monotonic (True-then-False or False-then-True over the range), bisect_left finds the boundary. Same template works for: first peak (LC 162), min capacity that fits k partitions (LC 875 Koko), min/max satisfying some constraint.

Hashing (map / set)

Trade a scan for a hash (cost nuance in Data Structures). Shapes:

Heap / top-k

heapq (min-heap; API in Data Structures). Recurring patterns:

Stack & monotonic stack

Intervals

Sort first, then sweep once — the sort key is the whole game:

Recursion / divide & conquer

Split into self-similar sub-problems, solve, combine: Euclidean GCD, merge sort, quickselect, "halve the range." Watch recursion depth (Python's default limit is 1000). LC 1071.

Backtracking

Enumerate permutations / combinations / subsets: recurse, try each choice, undo before the next (push/pop a shared mutable path). Complexity is output-bounded (O(n!) or O(2ⁿ)). For combinations (order-free, no dups), pass a start index and iterate range(start, end) — dedupes by construction. LC 17, 216, 46.

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])     # snapshot — copy, don't store the live list
        return
    for c in choices:
        path.append(c)
        backtrack(path, remaining(choices, c))
        path.pop()                  # undo

Iterative graph traversal templates

Two shapes, one per algorithm. Naming matches what the set actually contains.

# DFS — mark on POP, name `visited`. Stack may briefly hold dupes; pop-check catches them.
visited = set()
stack = [(start, initial_state)]          # state = whatever per-path value you carry (depth, product, etc.)
while stack:
    node, state = stack.pop()
    if node in visited:                   # load-bearing dedupe guard
        continue
    visited.add(node)
    if node == target:
        return state                      # found
    for nbr, edge_data in graph[node]:
        if nbr not in visited:            # optional push-time optimization (smaller stack)
            stack.append((nbr, combine(state, edge_data)))
# stack exhausted, target unreachable
# BFS — mark on PUSH, name `seen`. Required for level tracking (len(queue) must reflect unique nodes).
from collections import deque
seen = {start}                            # seed marking — required because we mark before pop
queue = deque([start])
depth = 0
while queue:
    for _ in range(len(queue)):           # snapshot one level; correctness depends on no dupes
        node = queue.popleft()
        if node == target:
            return depth
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr)
                queue.append(nbr)
    depth += 1
# queue exhausted, target unreachable

Why the split: BFS's level snapshot (for _ in range(len(queue))) requires the queue to contain exactly one entry per unique node at that level, so mark-on-push is mandatory. DFS has no level concept, and mark-on-pop avoids the seed-marking step. Pick the template that matches the algorithm; don't mix.

Trees

Almost always DFS or BFS over TreeNode.

Trie

Prefix tree for "repeated prefix matches in a word set." Two-class composition: a Trie holding TrieNodes (children = {} dict + is_end bool); the character is the dict key, not stored on the node. All ops O(L). Walk-or-create: node = node.children.setdefault(c, TrieNode()). Autocomplete (top-k lex-smallest per prefix): walk the prefix, then bounded-DFS sorted(node.children) collecting ≤k — or precompute ≤k refs per node during a sorted insert. LC 208, 1268. (Class-design detail in python_concepts.md.)

2D grids

# Init a 2D grid of zeros (m rows, n cols).
grid = [[0] * n for _ in range(m)]    # CORRECT — m independent rows

# DO NOT DO THIS — bug source:
grid = [[0] * n] * m                  # WRONG — m references to ONE row
                                      # grid[0][1] = 1 mutates every row!
# Reason: `*` copies references. Inner [0]*n is one mutable list; outer * m
# just creates pointers to it. List comprehension re-evaluates the inner
# expression each iteration, producing independent lists.

# Iterate over a grid:
for r in range(len(grid)):
    for c in range(len(grid[0])):
        ...

# Four-directional moves (up, down, left, right) — canonical:
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n:
        ...   # in-bounds neighbor

# Eight-directional (with diagonals): [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

Dynamic programming

When the recurrence isn't obvious, use the decision-tree-with-state framing:

  1. Decision space at each step? Buy/sell/hold; place a tile; pick a digit; include or skip.
  2. What constrains which decisions are legal? Can only sell if holding; can't pick adjacent houses.
  3. The thing limiting legality = your extra state dimension beyond the step index. Depends only on the step → 1D; depends on "holding?" / "yesterday's color?" / "capacity left?" → another dimension.
  4. Write solve(step, state) — try every legal action, recurse on (next_step, new_state), combine today's impact with the return; take max/sum/count.
  5. @cache it. State space O(n × |states|), so memoization collapses the 2ⁿ tree to polynomial.

solve(i, state) returns "the optimal value from step i to the end, given the current state" — self-similar, no global accumulator. Reach for top-down @cache first — easier to derive than the bottom-up table, identical complexity.

Recurrence shapes seen:

Siblings: knapsack (state = remaining capacity), regex/wildcard (state = position in pattern), cooldown / k-transaction stock (LC 309, 188).

Greedy

Commit to the locally-optimal choice, never reconsider. Valid only when:

  1. Greedy choice property — the obvious-best choice now is part of some global optimum.
  2. Optimal substructure — what's left after the choice is the same problem (shared with DP; greedy commits, DP explores).

When to try it: maximize/minimize a count under a constraint; a natural ordering (sort by end/deadline/ratio) makes the best pick obvious; choices don't entangle with the future.

Confirm before trusting:

Bit manipulation

Operators + the idioms that recur. Negative-int behavior (infinite two's complement, bin() display, & 0xFFFFFFFF masking) lives in python_concepts.md.

# OPERATORS
a & b     # AND  — 1 where both bits 1      5 & 3 = 1
a | b     # OR   — 1 where either bit 1      5 | 3 = 7
a ^ b     # XOR  — 1 where bits differ       5 ^ 3 = 6
~a        # NOT  — flip all bits             ~5 = -6   (identity: ~n == -n - 1)
a << k    # left shift   — ×2^k
a >> k    # right shift  — //2^k (floor)

# CORE IDIOMS (memorize — these recur)
n & 1               # is n odd? (lowest bit set?)
n >> 1              # drop the lowest bit (== n // 2)
n & (n - 1)         # clear the LOWEST set bit → popcount loop; power-of-2 check ((n & n-1)==0)
n & -n              # ISOLATE the lowest set bit
x ^ x == 0          # self-cancel;  x ^ 0 == x (identity)

# READ / SET / CLEAR bit i
(n >> i) & 1        # read bit i
n |= (1 << i)       # set bit i
n &= ~(1 << i)      # clear bit i

# POPCOUNT (number of set bits)
bin(n).count('1')           # cheap one-liner
n.bit_count()               # Py3.10+ builtin
# Brian Kernighan: while n: n &= n - 1; count += 1   → O(#set bits), not O(#bits)
# DP recurrence over 0..n: bits[i] = bits[i >> 1] + (i & 1)

# XOR "find the loner" — every element paired except one:
acc = 0
for x in nums: acc ^= x     # pairs cancel (x^x=0); the unpaired value survives

Sorting & custom keys

# sorted() returns a NEW list; list.sort() mutates in place and returns None (don't assign it)
sorted(xs)                          # ascending, new list
sorted(xs, reverse=True)            # descending
xs.sort()                           # in place

# key= : sort by a DERIVED value (the key function is called once per element)
sorted(words, key=len)                       # by length
sorted(intervals, key=lambda x: x[1])        # by END  ← the intervals-greedy pattern
sorted(intervals, key=lambda x: x[0])        # by start
sorted(pairs, key=lambda p: p[1], reverse=True)

# lambda = anonymous inline function: `lambda args: expr` — body is ONE expression, implicit return.
key=lambda x: x[1]      # exactly equivalent to:  def f(x): return x[1]

# MULTI-KEY — return a TUPLE: sort by first element, ties broken by second, then third, ...
sorted(people, key=lambda p: (p.age, p.name))     # age asc, then name asc
sorted(items,  key=lambda x: (-x.score, x.name))  # score DESC, then name ASC
#   negate a numeric field to flip just that field's direction inside the tuple

# STABILITY — Python's sort is stable: equal keys keep their original relative order.
#   lets you multi-pass: sort by secondary key first, then by primary key.

# key= also works on min / max (and heapq.nlargest / nsmallest):
max(intervals, key=lambda x: x[1] - x[0])    # widest interval
min(words, key=len)
# GOTCHA: heapq.heappush/heappop have NO key= param — push (sort_key, item) tuples instead.

# operator.itemgetter / attrgetter — faster, cleaner than lambda for plain field access:
from operator import itemgetter, attrgetter
sorted(intervals, key=itemgetter(1))         # same as lambda x: x[1]
sorted(people, key=attrgetter('age'))

Indexing & slicing

Iteration

Interview hygiene