Coding deep dives — the hard-topic refresher

Each pattern section is laid out the same way so you can skim it under time pressure:

The 30-second pattern decoder

Read the prompt, scan for a signal phrase, name the pattern, state the complexity. Only then start coding.

Complexity refresher

State the bound out loud before coding. The interviewer cares more that you know the cost than that you find the optimum first.

Two pointers — recognition + template

Signal: sorted array, "find a pair/triplet", "in-place" with no extra space, "partition", "merge two sorted things". The two pointers move toward each other (opposite ends) or in the same direction (slow/fast).

# Opposite-ends template (sorted input): find pair summing to target
def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1          # need bigger -> move left pointer right
        else:
            hi -= 1          # need smaller -> move right pointer left
    return []                # O(n) time, O(1) space

Worked: Two Sum (1) and 3Sum (15)

Two Sum on an unsorted array is a hashmap problem (one pass, $O(n)$). 3Sum sorts then fixes one element and runs the opposite-ends two-pointer on the rest, with dedup.

# Two Sum (LC 1) -- unsorted -> hashmap of value -> index
def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []                      # O(n) time, O(n) space

# 3Sum (LC 15) -- triplets summing to 0, no duplicate triplets
def three_sum(nums):
    nums.sort()                    # O(n log n)
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:            # smallest is positive -> impossible
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue               # skip duplicate anchor
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                # skip duplicates on both sides
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return res                     # O(n^2) time, O(1) extra (ignoring output)

Complexity: sort is $O(n \log n)$, the nested two-pointer scan is $O(n^2)$, so total $O(n^2)$.

Worked: Trapping Rain Water (42)

Signal: "water trapped between bars" — each index holds min(maxLeft, maxRight) - height[i]. The two-pointer trick: whichever side has the smaller running max is the bottleneck, so advance that side and you can resolve its water immediately.

def trap(height):
    lo, hi = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while lo < hi:
        if height[lo] < height[hi]:
            # left bar is the bottleneck -> left_max fully decides
            left_max = max(left_max, height[lo])
            water += left_max - height[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            water += right_max - height[hi]
            hi -= 1
    return water                   # O(n) time, O(1) space

Sliding window — recognition + template

Signal: "longest / shortest / count of contiguous subarray or substring such that …". The window [left, right] grows on the right; when it violates the constraint, shrink from the left. Track an answer as you go.

# Generic variable-size window
def window(s):
    from collections import defaultdict
    count = defaultdict(int)
    left = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] += 1                 # 1) include s[right]
        while WINDOW_IS_INVALID(count): # 2) shrink until valid
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        best = max(best, right - left + 1)  # 3) record answer
    return best

Worked: Longest Substring with At Most K Distinct (340)

def longest_k_distinct(s, k):
    from collections import defaultdict
    count = defaultdict(int)
    left = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:          # too many distinct -> shrink
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best                        # O(n) time, O(k) space

Worked: Minimum Window Substring (76)

This is the hard "shrink-to-minimum" variant. Maintain a need-count of t and a counter have of how many required chars are currently satisfied. When all are satisfied, shrink to record a candidate minimum.

def min_window(s, t):
    from collections import Counter
    if not t or not s:
        return ""
    need = Counter(t)
    required = len(need)            # number of distinct chars to satisfy
    have = 0                        # how many distinct chars are satisfied
    window = {}
    left = 0
    best_len = float("inf")
    best = (0, 0)
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            have += 1
        while have == required:     # valid -> try to shrink
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best = (left, right)
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1
            left += 1
    l, r = best
    return s[l:r + 1] if best_len != float("inf") else ""
    # O(|s| + |t|) time, O(|t|) space

Worked: Product of Array Except Self (238)

Signal: "product/sum of all except current, no division." Two passes of prefix/suffix products.

def product_except_self(nums):
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):             # res[i] = product of everything left of i
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1): # multiply in product of everything right of i
        res[i] *= suffix
        suffix *= nums[i]
    return res                     # O(n) time, O(1) extra (output excluded)

Hashmap idioms in Python

from collections import Counter, defaultdict

Counter("aabbc")            # Counter({'a':2,'b':2,'c':1})
Counter(nums).most_common(k) # k highest-frequency (val, count) pairs

d = defaultdict(list)        # auto-creates [] on first access
d[key].append(x)

groups = defaultdict(list)   # group anagrams: key on sorted letters
for w in words:
    groups["".join(sorted(w))].append(w)

Prefix sum — template

Define P[i] = nums[0] + ... + nums[i-1] with P[0] = 0. Then the sum of nums[l..r] is P[r+1] - P[l]. For "subarray sum equals k," reframe: a subarray ending at i has sum k iff some earlier prefix equals running - k.

# Subarray Sum Equals K (LC 560): count subarrays summing to k
def subarray_sum(nums, k):
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1                 # empty prefix
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen[running - k]  # prefixes that make sum == k
        seen[running] += 1
    return count                # O(n) time, O(n) space

Worked: Continuous Subarray Sum / divisibility (523)

Signal: "subarray whose sum is a multiple of k." Two prefix sums with the same remainder mod k bracket a subarray divisible by k. Store the earliest index per remainder to enforce a minimum length of 2.

def check_subarray_sum(nums, k):
    first_index = {0: -1}       # remainder -> earliest index
    running = 0
    for i, x in enumerate(nums):
        running += x
        r = running % k
        if r in first_index:
            if i - first_index[r] >= 2:
                return True
        else:
            first_index[r] = i  # keep earliest only
    return False                # O(n) time, O(min(n,k)) space

The canonical template (lower_bound)

Search the boundary between False and True. This single shape covers "find first index ≥ target," "find insertion point," and "search on answer." It avoids the classic mid/lo/hi off-by-ones because the invariant is explicit: everything below lo is False, everything at/above hi is True.

# Returns the first index in [0, n] where predicate(i) is True.
# predicate must be monotone: F F F T T T
def lower_bound(n, predicate):
    lo, hi = 0, n               # hi is exclusive / sentinel "all True"
    while lo < hi:
        mid = (lo + hi) // 2
        if predicate(mid):
            hi = mid            # mid might be the answer -> keep it
        else:
            lo = mid + 1        # mid is too small -> discard it
    return lo                   # O(log n) probes

# Standard "find x in sorted nums" via lower_bound:
def search(nums, x):
    i = lower_bound(len(nums), lambda i: nums[i] >= x)
    return i if i < len(nums) and nums[i] == x else -1

For Python's batteries-included version, use bisect.bisect_left / bisect.bisect_right directly when allowed.

Worked: Search in Rotated Sorted Array (33, 81)

Signal: sorted-but-rotated. At each step one half is sorted; decide which half the target lies in.

# LC 33: no duplicates
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:        # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1                            # O(log n)

LC 81 allows duplicates, which breaks the "one half is sorted" test when nums[lo] == nums[mid] == nums[hi]. Handle it by shrinking both ends by one (lo += 1; hi -= 1), degrading worst case to $O(n)$.

Worked: Find Peak Element (162)

No global sort, but neighbors are unequal — you can still binary search by walking uphill.

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1        # peak is to the right
        else:
            hi = mid            # peak is mid or to the left
    return lo                   # O(log n)

Search on the answer — the highest-leverage pattern

Signal: "minimize the maximum," "maximize the minimum," "smallest capacity/speed/days such that we can …." Don't search the array — search the answer value, with a monotone feasibility check.

# Koko Eating Bananas (LC 875): minimum eating speed to finish in h hours.
import math
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)
    # feasible(speed) is monotone: faster speed -> fewer hours
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= h:
            hi = mid            # mid works -> try slower
        else:
            lo = mid + 1        # too slow -> speed up
    return lo
    # O(n log(max_pile)) time

class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

Reverse a linked list (206)

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # save the rest
        cur.next = prev     # rewire backwards
        prev = cur          # advance prev
        cur = nxt           # advance cur
    return prev             # new head; O(n) time, O(1) space

Fast/slow cycle detection — Floyd (141, 142)

Signal: "does the list have a cycle / where does it start." Slow moves 1, fast moves 2; they meet inside the cycle iff one exists. To find the entry, reset one pointer to head and advance both by 1 — they meet at the cycle start (a clean number-theory result).

# LC 141: detect cycle
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False            # O(n) time, O(1) space

# LC 142: return the node where the cycle begins (or None)
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                 # meeting point
            ptr = head
            while ptr is not slow:       # advance both by 1
                ptr = ptr.next
                slow = slow.next
            return ptr                   # cycle entry
    return None

Worked: Merge k Sorted Lists (23) — ties to heap

Signal: "merge k sorted things." Keep a min-heap of the current head of each list; pop the smallest, push its successor. Push the list index as a tiebreaker so Python never tries to compare ListNode objects.

import heapq
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))  # (val, idx, node)
    dummy = tail = ListNode()
    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
    # N = total nodes, k = lists -> O(N log k) time, O(k) heap space

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Traversals (94 inorder, 102 level-order, 103 zigzag)

# Inorder (LC 94) -- iterative with explicit stack
def inorder(root):
    res, stack, cur = [], [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

# Level-order (LC 102) -- BFS by level
from collections import deque
def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):      # snapshot this level's size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

# Zigzag (LC 103) -- reverse alternate levels
def zigzag(root):
    res = level_order(root)
    for i in range(len(res)):
        if i % 2 == 1:
            res[i].reverse()
    return res

Depth + Validate BST (98)

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# LC 98: validate BST by passing down the allowed (low, high) bounds
def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Lowest Common Ancestor (235 BST, 236 general)

# LC 235: BST -- walk down using the ordering
def lca_bst(root, p, q):
    cur = root
    while cur:
        if p.val < cur.val and q.val < cur.val:
            cur = cur.left
        elif p.val > cur.val and q.val > cur.val:
            cur = cur.right
        else:
            return cur          # split point = LCA. O(h) time

# LC 236: general tree -- post-order; first node with p,q in different subtrees
def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root             # p,q split here -> this is the LCA
    return left or right        # both on one side

Path sum family (112, 113, 124, 437)

# LC 112: root-to-leaf path summing to target?
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return target == root.val
    rest = target - root.val
    return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

# LC 124: max path sum (path may bend at any node, need not touch root/leaf)
def max_path_sum(root):
    best = float("-inf")
    def gain(node):
        nonlocal best
        if not node:
            return 0
        # clamp negative contributions to 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)  # path bending at node
        return node.val + max(left, right)          # extendable upward
    gain(root)
    return best                 # O(n) time

# LC 437: count downward paths summing to target (prefix sum on a tree)
def path_sum_iii(root, target):
    from collections import defaultdict
    prefix = defaultdict(int)
    prefix[0] = 1
    def dfs(node, running):
        if not node:
            return 0
        running += node.val
        count = prefix[running - target]
        prefix[running] += 1
        count += dfs(node.left, running) + dfs(node.right, running)
        prefix[running] -= 1            # backtrack: leave this path
        return count
    return dfs(root, 0)         # O(n) time

Construct from traversals (105, 106)

The first preorder element is the root; its index in inorder splits inorder into left/right subtrees. Use a hashmap from value→inorder index for $O(1)$ splits.

# LC 105: build tree from preorder + inorder
def build_tree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    self_pre = iter(preorder)
    def helper(lo, hi):
        if lo > hi:
            return None
        root_val = next(self_pre)       # consume preorder left-to-right
        root = TreeNode(root_val)
        mid = idx[root_val]
        root.left = helper(lo, mid - 1)
        root.right = helper(mid + 1, hi)
        return root
    return helper(0, len(inorder) - 1)  # O(n) time

Serialize / deserialize (297)

Preorder with explicit null markers makes the structure unambiguous; deserialize by consuming the same preorder stream.

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node:
                out.append("#")          # null marker
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(out)

    def deserialize(self, data):
        vals = iter(data.split(","))
        def build():
            v = next(vals)
            if v == "#":
                return None
            node = TreeNode(int(v))
            node.left = build()
            node.right = build()
            return node
        return build()                   # O(n) both ways

heapq idioms

import heapq
h = []
heapq.heappush(h, 5)
smallest = heapq.heappop(h)       # min
heapq.heapify(lst)                # O(n) in place
heapq.nlargest(k, nums)           # convenience: top k
heapq.nsmallest(k, nums)

# Max-heap: push negatives
heapq.heappush(h, -x); top = -heapq.heappop(h)

# Tuples compare lexicographically; add a tiebreaker index for non-comparable payloads
heapq.heappush(h, (priority, tie_index, payload))

Worked: Top K Frequent Elements (347)

import heapq
from collections import Counter
def top_k_frequent(nums, k):
    freq = Counter(nums)
    # size-k min-heap of (count, value); evict smallest count
    return heapq.nlargest(k, freq.keys(), key=freq.get)
    # O(n log k) with a size-k heap (nlargest uses one internally)

Worked: Find Median from Data Stream (295)

Signal: "median of a running stream." Maintain two heaps: a max-heap of the lower half and a min-heap of the upper half, kept balanced in size. The median is the top of one (odd) or the average of both tops (even).

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (store negatives) -> lower half
        self.hi = []   # min-heap -> upper half

    def addNum(self, num):
        heapq.heappush(self.lo, -num)            # push to lower half
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # move its max to hi
        if len(self.hi) > len(self.lo):          # rebalance: lo >= hi in size
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2
    # addNum O(log n), findMedian O(1)

Grid DFS / BFS templates

from collections import deque
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def in_bounds(r, c, R, C):
    return 0 <= r < R and 0 <= c < C

# DFS flood fill (recursive)
def dfs(grid, r, c, R, C, visited):
    visited.add((r, c))
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc, R, C) and (nr, nc) not in visited and grid[nr][nc] == "1":
            dfs(grid, nr, nc, R, C, visited)

# BFS shortest path on an unweighted grid
def bfs_dist(grid, start, R, C):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        # process (r,c) at distance d ...
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if in_bounds(nr, nc, R, C) and (nr, nc) not in seen and grid[nr][nc] != "#":
                seen.add((nr, nc))
                q.append(((nr, nc), d + 1))

Worked: Number of Islands (200)

def num_islands(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    seen = set()
    count = 0
    def sink(r, c):                  # DFS to mark a whole island
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            for dr, dc in DIRS:
                nr, nc = cr + dr, cc + dc
                if (in_bounds(nr, nc, R, C) and grid[nr][nc] == "1"
                        and (nr, nc) not in seen):
                    seen.add((nr, nc))
                    stack.append((nr, nc))
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1" and (r, c) not in seen:
                seen.add((r, c))
                sink(r, c)
                count += 1
    return count                     # O(R*C) time and space

Worked: Surrounded Regions (130)

The trick: regions touching the border can't be captured. DFS from every border 'O' to mark survivors, then flip the rest.

def solve(board):
    if not board:
        return
    R, C = len(board), len(board[0])
    def mark(r, c):
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            if not in_bounds(cr, cc, R, C) or board[cr][cc] != "O":
                continue
            board[cr][cc] = "S"      # survivor
            for dr, dc in DIRS:
                stack.append((cr + dr, cc + dc))
    for r in range(R):
        mark(r, 0); mark(r, C - 1)
    for c in range(C):
        mark(0, c); mark(R - 1, c)
    for r in range(R):
        for c in range(C):
            board[r][c] = "O" if board[r][c] == "S" else "X"

Multi-source BFS (e.g. Rotting Oranges 994)

def oranges_rotting(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))     # seed ALL sources at once
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        minutes += 1
        for _ in range(len(q)):      # one ring per minute
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if in_bounds(nr, nc, R, C) and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
    return -1 if fresh else minutes

Worked: Word Ladder (127) REDDIT

Signal: shortest transformation sequence — BFS where neighbors are one-letter edits. Use wildcard buckets (h*t) to find neighbors in $O(L)$ rather than scanning the whole word list. Word Ladder is a confirmed Reddit coding problem.

from collections import deque, defaultdict
def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0
    L = len(begin)
    # generic pattern -> all words matching it
    buckets = defaultdict(list)
    for w in words:
        for i in range(L):
            buckets[w[:i] + "*" + w[i+1:]].append(w)
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(L):
            pat = word[:i] + "*" + word[i+1:]
            for nxt in buckets[pat]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, steps + 1))
            buckets[pat] = []        # prune: never revisit this bucket
    return 0
    # O(N * L^2) time (N words, length L)

Word Ladder II (126) additionally reconstructs all shortest paths: do a BFS to build a parents map of predecessors at each level, then backtrack from end to enumerate paths.

Adjacency representations

from collections import defaultdict, deque

# Adjacency list (preferred for sparse graphs): O(V+E) space
graph = defaultdict(list)
for u, v in edges:          # directed edge u -> v
    graph[u].append(v)
    # for an undirected graph also add: graph[v].append(u)

# Adjacency matrix: O(V^2) space; fine for dense / small V
adj = [[0] * V for _ in range(V)]
for u, v in edges:
    adj[u][v] = 1

Directed cycle detection — 3-color DFS

Color each node WHITE (unvisited), GRAY (on the current DFS stack), or BLACK (fully done). A back edge to a GRAY node is a cycle: GRAY means "this node is an ancestor in the current path." Reaching a BLACK node is fine — it was finished on a different path with no cycle through it.

WHITE, GRAY, BLACK = 0, 1, 2
def has_cycle_directed(num_nodes, graph):
    color = [WHITE] * num_nodes
    def dfs(u):
        color[u] = GRAY                 # entering -> on current path
        for v in graph[u]:
            if color[v] == GRAY:        # back edge -> cycle!
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK                # leaving -> fully processed
        return False
    for u in range(num_nodes):
        if color[u] == WHITE and dfs(u):
            return True
    return False
    # O(V + E) time, O(V) space (recursion + colors)

Topological sort — post-order DFS

The same 3-color DFS yields a topo order: append a node to the output when it finishes (turns BLACK), then reverse. If a cycle is found, no valid order exists.

def topo_sort_dfs(num_nodes, graph):
    color = [WHITE] * num_nodes
    order = []
    has_cycle = False
    def dfs(u):
        nonlocal has_cycle
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                has_cycle = True
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)                 # finished -> push
    for u in range(num_nodes):
        if color[u] == WHITE:
            dfs(u)
    if has_cycle:
        return []                       # no topo order
    return order[::-1]                  # reverse finish order
    # O(V + E)

Topological sort — Kahn's BFS (in-degree)

Repeatedly emit nodes with in-degree 0, decrementing their neighbors. If you emit fewer than V nodes, a cycle blocked the rest — so Kahn's detects directed cycles for free.

def topo_sort_kahn(num_nodes, graph):
    indeg = [0] * num_nodes
    for u in range(num_nodes):
        for v in graph[u]:
            indeg[v] += 1
    q = deque(u for u in range(num_nodes) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:           # all prereqs satisfied
                q.append(v)
    if len(order) != num_nodes:
        return []                       # cycle -> impossible
    return order                        # O(V + E)

Union-Find — undirected cycle detection

For an undirected graph, walk the edges and union the endpoints. If both endpoints are already in the same set before you union them, this edge closes a cycle. Path compression + union by rank gets each op to near-constant $O(\alpha(n))$.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))    # each node is its own root
        self.rank = [0] * n             # tree height upper bound

    def find(self, x):
        # path compression: point everything straight at the root
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                # already connected -> cycle edge
        # union by rank: attach shorter tree under taller
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True                     # merged two distinct components

def has_cycle_undirected(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):
            return True                 # this edge formed a cycle
    return False

Directed vs undirected cycle detection — the key distinction

# Undirected cycle detection via DFS (skip parent edge)
def has_cycle_undirected_dfs(n, graph):
    seen = [False] * n
    def dfs(u, parent):
        seen[u] = True
        for v in graph[u]:
            if not seen[v]:
                if dfs(v, u):
                    return True
            elif v != parent:           # visited AND not where we came from
                return True             # -> cycle
        return False
    for u in range(n):
        if not seen[u] and dfs(u, -1):
            return True
    return False

Worked: Course Schedule I & II (207, 210)

"Can you finish all courses given prerequisites?" is "is this directed graph a DAG (no cycle)?" The order to take them is its topological sort.

# LC 207: can finish? -> DAG check via Kahn's
def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    indeg = [0] * num_courses
    for course, prereq in prerequisites:   # must take prereq before course
        graph[prereq].append(course)       # edge prereq -> course
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return taken == num_courses            # all reachable -> no cycle

# LC 210: return a valid order (or [] if impossible)
def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indeg = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == num_courses else []
    # O(V + E)

Worked: Alien Dictionary (269)

Given words sorted in an unknown alphabet, derive the letter order. The first differing character between adjacent words gives a directed edge (earlier letter → later letter); topo-sort the letters. Edge case: if a longer word precedes its own prefix (["abc","ab"]), the input is invalid.

def alien_order(words):
    graph = defaultdict(set)
    indeg = {c: 0 for w in words for c in w}
    for a, b in zip(words, words[1:]):
        # invalid: "abc" before "ab"
        if len(a) > len(b) and a.startswith(b):
            return ""
        for ca, cb in zip(a, b):
            if ca != cb:
                if cb not in graph[ca]:
                    graph[ca].add(cb)
                    indeg[cb] += 1
                break                   # only the FIRST diff gives an edge
    q = deque(c for c in indeg if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return "".join(order) if len(order) == len(indeg) else ""  # "" if cycle

Worked: Clone Graph (133)

def clone_graph(node):
    if not node:
        return None
    clones = {}                          # original -> copy
    def dfs(orig):
        if orig in clones:
            return clones[orig]
        copy = Node(orig.val)
        clones[orig] = copy              # register BEFORE recursing (handles cycles)
        for nb in orig.neighbors:
            copy.neighbors.append(dfs(nb))
        return copy
    return dfs(node)                     # O(V + E)

Worked: Redundant Connection (684, 685)

LC 684 (undirected): given a tree plus one extra edge, find the edge that creates the cycle — exactly the first union that returns False.

def find_redundant(edges):
    dsu = DSU(len(edges) + 1)            # nodes are 1..n
    for u, v in edges:
        if not dsu.union(u, v):
            return [u, v]                # this edge closed the cycle
    return []

LC 685 (directed) is harder: a node may now have in-degree 2 or there's a cycle. Detect a node with two parents; if removing the second candidate still leaves a cycle, the answer is the first candidate instead. It's a careful case split on top of union-find.

Worked: Accounts Merge (721)

Union accounts that share any email; then group emails by their set root. Map each email to an owner name and to an index so you can union by index.

def accounts_merge(accounts):
    dsu = DSU(len(accounts))
    email_to_acct = {}                   # email -> first account index seen
    for i, acct in enumerate(accounts):
        for email in acct[1:]:
            if email in email_to_acct:
                dsu.union(i, email_to_acct[email])
            else:
                email_to_acct[email] = i
    # gather emails under each component root
    merged = defaultdict(set)
    for email, i in email_to_acct.items():
        merged[dsu.find(i)].add(email)
    res = []
    for root, emails in merged.items():
        name = accounts[root][0]
        res.append([name] + sorted(emails))
    return res

Worked: Number of Provinces (547)

Count connected components in an undirected graph given as an adjacency matrix — a direct union-find (or DFS) application. Each remaining distinct root is one province.

def find_circle_num(is_connected):
    n = len(is_connected)
    dsu = DSU(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                dsu.union(i, j)
    return len({dsu.find(i) for i in range(n)})  # distinct roots = components

The universal template

def backtrack(state, choices):
    if is_complete(state):
        record(state)                    # found a full solution
        return
    for choice in choices:
        if not is_valid(state, choice):  # PRUNE invalid branches
            continue
        make(state, choice)              # CHOOSE
        backtrack(state, next_choices)   # EXPLORE
        undo(state, choice)             # UN-CHOOSE (backtrack)

Always pass an index (where you are in the input) plus the partial solution. Recording a solution usually means appending a copy (path[:]) because path keeps mutating.

Subsets (78) and Subsets II with duplicates (90)

# LC 78: all subsets (input distinct)
def subsets(nums):
    res = []
    def bt(start, path):
        res.append(path[:])              # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # choose
            bt(i + 1, path)              # explore (i+1: no reuse)
            path.pop()                   # un-choose
    bt(0, [])
    return res                           # O(2^n * n)

# LC 90: with duplicates -> sort, then skip equal siblings
def subsets_with_dup(nums):
    nums.sort()
    res = []
    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                 # DEDUP: skip duplicate sibling choice
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()
    bt(0, [])
    return res

The dedup rule is precise: i > start and nums[i] == nums[i-1] skips a duplicate only when it is a sibling (same recursion level), not when it is being chosen the first time at a deeper level.

Permutations (46) and with duplicates (47)

# LC 46: all permutations (distinct)
def permute(nums):
    res = []
    used = [False] * len(nums)
    def bt(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt(path)
            path.pop()
            used[i] = False
    bt([])
    return res                           # O(n! * n)

# LC 47: with duplicates -> sort, skip dup unless its twin was just used
def permute_unique(nums):
    nums.sort()
    res = []
    used = [False] * len(nums)
    def bt(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # dedup: skip nums[i] if equal twin to its left is unused
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            bt(path)
            path.pop()
            used[i] = False
    bt([])
    return res

Combination Sum (39, 40)

# LC 39: unlimited reuse of each candidate
def combination_sum(candidates, target):
    res = []
    candidates.sort()                    # enables prune
    def bt(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                    # PRUNE: sorted -> rest too big
            path.append(candidates[i])
            bt(i, path, remaining - candidates[i])  # i (not i+1): reuse allowed
            path.pop()
    bt(0, [], target)
    return res

# LC 40: each number used once + duplicates in input
def combination_sum2(candidates, target):
    res = []
    candidates.sort()
    def bt(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                 # DEDUP siblings
            if candidates[i] > remaining:
                break                    # PRUNE
            path.append(candidates[i])
            bt(i + 1, path, remaining - candidates[i])  # i+1: no reuse
            path.pop()
    bt(0, [], target)
    return res

Worked: Word Search (79)

Backtracking on a grid: DFS from each cell, marking visited cells with a sentinel and restoring them on the way out.

def exist(board, word):
    R, C = len(board), len(board[0])
    def bt(r, c, k):
        if k == len(word):
            return True
        if (r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[k]):
            return False
        tmp = board[r][c]
        board[r][c] = "#"               # mark visited (choose)
        found = (bt(r + 1, c, k + 1) or bt(r - 1, c, k + 1) or
                 bt(r, c + 1, k + 1) or bt(r, c - 1, k + 1))
        board[r][c] = tmp               # restore (un-choose)
        return found
    return any(bt(r, c, 0) for r in range(R) for c in range(C))
    # O(R*C * 4^L) worst case (L = word length)

N-Queens (51) — pruning with diagonal sets

Place one queen per row; track occupied columns and both diagonals in sets so validity is $O(1)$ per check. Diagonal identity: cells on the same "/" diagonal share r + c; same "\" diagonal share r - c.

def solve_n_queens(n):
    res = []
    cols = set()
    diag1 = set()      # r + c (anti-diagonal)
    diag2 = set()      # r - c (main diagonal)
    board = []
    def bt(r):
        if r == n:
            res.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r + c) in diag1 or (r - c) in diag2:
                continue                 # PRUNE attacked squares
            cols.add(c); diag1.add(r + c); diag2.add(r - c)
            board.append(["."] * n)
            board[r][c] = "Q"
            bt(r + 1)
            board.pop()                  # un-choose
            cols.remove(c); diag1.remove(r + c); diag2.remove(r - c)
    bt(0)
    return res

Palindrome Partitioning (131)

def partition(s):
    res = []
    def is_pal(sub):
        return sub == sub[::-1]
    def bt(start, path):
        if start == len(s):
            res.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if is_pal(piece):            # only branch on valid prefixes (prune)
                path.append(piece)
                bt(end, path)
                path.pop()
    bt(0, [])
    return res

Is this a DP problem? — decision tree

1. Does it ask for a min / max / count / "can you" over a sequence of decisions? (yes → strong DP signal)
2. Can you make one decision at a time, leaving a smaller version of the same problem? (yes → DP)
3. Do different decision paths reach the same subproblem? (yes → memoize; if no, it's plain divide-and-conquer or greedy)
4. Is there a greedy local rule that's provably optimal? (yes → prefer greedy; DP is the fallback when greedy fails, e.g. Coin Change)

The backtracking → memoization → tabulation pipeline

Use Climbing Stairs (70) to see all three forms of the same recurrence $f(n) = f(n-1) + f(n-2)$.

# 1) Brute-force recursion (exponential -- the recurrence, made explicit)
def climb_recur(n):
    if n <= 2:
        return n
    return climb_recur(n - 1) + climb_recur(n - 2)   # O(2^n)

# 2) Top-down memoization -- add a cache; now O(n)
from functools import cache
@cache
def climb_memo(n):
    if n <= 2:
        return n
    return climb_memo(n - 1) + climb_memo(n - 2)

# 3) Bottom-up tabulation -- O(n) time, O(1) space (rolling)
def climb_tab(n):
    if n <= 2:
        return n
    a, b = 1, 2            # f(1), f(2)
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

The lesson: derive the recurrence with recursion first, then mechanically add a cache. Tabulation is just the same recurrence evaluated in dependency order. In interviews, top-down memoization is usually enough and is easier to derive under pressure.

The recurrence-derivation method

For each state, ask: "what is the last decision, and what subproblem remains after it?" Write the answer as a max/min/sum over the choices for that last decision.

1D DP — House Robber (198, 213)

State: dp[i] = max loot from houses 0..i. Last decision: rob house i (then skip i-1) or skip it. $dp[i] = \max(dp[i-1],\ dp[i-2] + nums[i])$.

def rob(nums):
    prev2, prev1 = 0, 0       # dp[i-2], dp[i-1]
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1              # O(n) time, O(1) space

# LC 213: houses in a circle -> first and last are adjacent.
# Run the line version twice: exclude the first, then exclude the last.
def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    return max(rob(nums[1:]), rob(nums[:-1]))

1D DP — Coin Change (322)

State: dp[a] = fewest coins to make amount a. Last decision: which coin is used last. $dp[a] = \min_{c \in coins}(dp[a - c] + 1)$, base dp[0]=0.

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount        # dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1
    # O(amount * len(coins)) time, O(amount) space

1D DP — Longest Increasing Subsequence (300)

State: dp[i] = length of LIS ending at i. $dp[i] = 1 + \max\{dp[j] : j < i,\ nums[j] < nums[i]\}$. The $O(n^2)$ DP is the clean answer; the $O(n \log n)$ patience-sorting version uses binary search.

# O(n^2) DP
def lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(n log n) -- maintain tails[k] = smallest tail of an increasing subseq of length k+1
import bisect
def lis_fast(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)          # extend
        else:
            tails[i] = x             # replace -> keep tails small
    return len(tails)

1D DP on strings — Word Break (139, 140)

State: dp[i] = can s[:i] be segmented? $dp[i] = \exists j < i: dp[j] \wedge s[j:i] \in dict$.

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                     # empty string is segmentable
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]                     # O(n^2 * L) checking substrings

Word Break II (140) returns all sentences; memoize a recursion that returns the list of suffix segmentations from each index.

Kadane — Maximum Subarray (53)

State: best_ending_here = max subarray sum ending at i. Either extend the previous run or start fresh at i. $cur = \max(nums[i],\ cur + nums[i])$.

def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)        # extend or restart
        best = max(best, cur)
    return best                      # O(n) time, O(1) space

2D DP — Unique Paths (62) and Edit Distance (72)

# LC 62: grid paths from top-left to bottom-right (right/down only)
def unique_paths(m, n):
    dp = [1] * n                     # first row: one way each
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]       # from above + from left
    return dp[-1]                    # O(m*n) time, O(n) space

# LC 72: edit distance (insert/delete/replace) to turn word1 into word2
def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    # dp[i][j] = edit distance between word1[:i] and word2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                 # delete all i chars
    for j in range(n + 1):
        dp[0][j] = j                 # insert all j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]            # match, free
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],       # delete from word1
                    dp[i][j - 1],       # insert into word1
                    dp[i - 1][j - 1],   # replace
                )
    return dp[m][n]                  # O(m*n)

2D DP — Longest Common Subsequence

State: dp[i][j] = LCS of a[:i] and b[:j]. If the last chars match, extend the diagonal; else take the better of dropping one char from either string.

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

0/1 Knapsack — the canonical bounded-choice DP

State: dp[w] = max value with capacity w using items considered so far. For 0/1 (each item once), iterate capacity downward so each item is used at most once.

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        w_i, v_i = weights[i], values[i]
        for w in range(capacity, w_i - 1, -1):   # DOWNWARD = use item once
            dp[w] = max(dp[w], dp[w - w_i] + v_i)
    return dp[capacity]             # O(n * capacity)

Regex / Wildcard matching (10, 44)

2D DP over (i, j) = does s[:i] match p[:j]. For regex, * means "zero or more of the preceding char"; handle the zero case (dp[i][j-2]) and the one-more case (match preceding char and consume one of s).

# LC 10: regex with '.' (any single) and '*' (zero+ of preceding)
def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # patterns like a*, a*b* can match empty string
    for j in range(1, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                # zero of preceding:
                dp[i][j] = dp[i][j - 2]
                # one+ of preceding (if it matches s[i-1]):
                if p[j - 2] == s[i - 1] or p[j - 2] == ".":
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]                 # O(m*n)

# LC 44: wildcard with '?' (any single) and '*' (any sequence incl. empty)
def is_match_wildcard(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 1]      # '*' can match empty
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                # '*' matches empty (dp[i][j-1]) or one more char (dp[i-1][j])
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

Interval DP — Burst Balloons (312)

State: dp[i][j] = max coins from bursting all balloons strictly between i and j. Key inversion: think of which balloon is burst last in (i, j) — then its neighbors are exactly the padded boundaries i and j, decoupling the two sides.

def max_coins(nums):
    balloons = [1] + nums + [1]      # pad both ends with virtual 1s
    n = len(balloons)
    dp = [[0] * n for _ in range(n)]
    # length = gap between i and j (exclusive interval grows outward)
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):    # k = LAST balloon burst in (i, j)
                coins = balloons[i] * balloons[k] * balloons[j]
                dp[i][j] = max(dp[i][j], dp[i][k] + coins + dp[k][j])
    return dp[0][n - 1]              # O(n^3)

The operator toolkit

def is_set(x, i):   return (x >> i) & 1 == 1
def set_bit(x, i):  return x | (1 << i)
def clear_bit(x, i):return x & ~(1 << i)
def toggle(x, i):   return x ^ (1 << i)
def is_power_of_two(x): return x > 0 and (x & (x - 1)) == 0

XOR — Single Number (136, 137)

Signal: "every element appears twice except one" → XOR everything; pairs cancel, the loner survives.

# LC 136: all appear twice except one
def single_number(nums):
    x = 0
    for n in nums:
        x ^= n            # a^a = 0, a^0 = a -> survivors only
    return x              # O(n) time, O(1) space

# LC 137: every element appears THREE times except one.
# Track bits seen once / twice with two accumulators.
def single_number_ii(nums):
    ones = twos = 0
    for n in nums:
        ones = (ones ^ n) & ~twos
        twos = (twos ^ n) & ~ones
    return ones

Counting bits (191, 338)

# LC 191: number of 1 bits (Brian Kernighan)
def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1        # drop the lowest set bit each step
        count += 1
    return count          # O(set bits)

# LC 338: count bits for every i in 0..n -- DP on x & (x-1)
def count_bits(n):
    dp = [0] * (n + 1)
    for x in range(1, n + 1):
        dp[x] = dp[x & (x - 1)] + 1   # one more bit than x with lowest cleared
    return dp             # O(n)

Missing Number (268)

XOR all indices 0..n with all values; everything pairs up except the missing index.

def missing_number(nums):
    x = len(nums)         # start with n (the index that has no value)
    for i, v in enumerate(nums):
        x ^= i ^ v
    return x              # O(n) time, O(1) space

Subset enumeration via bitmask

Each integer mask in 0..2^n-1 encodes a subset: bit i set means element i is included. This is the backbone of bitmask DP.

# Enumerate all 2^n subsets of nums
def all_subsets(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):              # 0 .. 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        res.append(subset)
    return res

# Enumerate all SUBMASKS of a given mask (classic bitmask-DP iteration)
def submasks(mask):
    sub = mask
    while sub:
        yield sub
        sub = (sub - 1) & mask              # next smaller submask
    yield 0

Bitmask DP example: the Traveling Salesman / "shortest path visiting all nodes" uses state dp[mask][i] = min cost having visited the set mask ending at node i, transition over the next unvisited node — $O(2^n \cdot n^2)$.

Reverse Bits (190) — Python width gotcha

Python ints have no fixed width, so you must specify 32 explicitly and mask back to 32 bits.

def reverse_bits(n):
    result = 0
    for _ in range(32):                     # fixed 32-bit width
        result = (result << 1) | (n & 1)    # pull lowest bit of n into result
        n >>= 1
    return result & 0xFFFFFFFF              # clamp to 32 bits

class TennisGame:
    POINTS = {0: "Love", 1: "15", 2: "30", 3: "40"}

    def __init__(self, player1="Player 1", player2="Player 2"):
        self.names = (player1, player2)
        self.scores = [0, 0]          # raw point counts

    def add_score(self, player):
        """player is 0 or 1."""
        if player not in (0, 1):
            raise ValueError("player must be 0 or 1")
        self.scores[player] += 1

    def get_score(self):
        """Return the human-readable score string."""
        p0, p1 = self.scores
        # 1) A player has won (4+ points and 2-point lead)
        if max(p0, p1) >= 4 and abs(p0 - p1) >= 2:
            winner = 0 if p0 > p1 else 1
            return f"Win for {self.names[winner]}"
        # 2) Deuce / advantage territory (both at 3+ points = 40-40)
        if p0 >= 3 and p1 >= 3:
            if p0 == p1:
                return "Deuce"
            leader = 0 if p0 > p1 else 1
            return f"Advantage {self.names[leader]}"
        # 3) Normal scoring: Love/15/30/40, leader's side first if differ
        s0, s1 = self.POINTS[p0], self.POINTS[p1]
        if p0 == p1:
            return f"{s0}-All"        # e.g. "15-All"
        return f"{s0}-{s1}"           # e.g. "30-15"

    def get_result(self):
        return self.get_score()

# Quick check
g = TennisGame("Alice", "Bob")
for _ in range(3): g.add_score(0)     # Alice -> 40
for _ in range(3): g.add_score(1)     # Bob   -> 40
print(g.get_score())                  # "Deuce"
g.add_score(0); print(g.get_score())  # "Advantage Alice"
g.add_score(0); print(g.get_score())  # "Win for Alice"

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}                 # key -> Node
        # sentinel head/tail to avoid null checks
        self.head = Node()              # MRU side
        self.tail = Node()              # LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):         # insert right after head (MRU)
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)              # move to front (just used)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_front(node)
        if len(self.cache) > self.cap:  # evict LRU (node before tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
    # get/put both O(1)

import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate            # tokens added per second
        self.capacity = capacity    # max burst
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self):
        now = time.monotonic()
        elapsed = now - self.last
        # refill proportional to elapsed time, capped at capacity
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True             # request permitted
        return False                # rate-limited
    # O(1) per request, O(1) memory


from collections import deque

class SlidingWindowLog:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window = window_seconds
        self.events = deque()       # request timestamps, oldest at left

    def allow(self):
        now = time.monotonic()
        # evict timestamps outside the window
        while self.events and self.events[0] <= now - self.window:
            self.events.popleft()
        if len(self.events) < self.limit:
            self.events.append(now)
            return True
        return False
    # amortized O(1) per request, O(requests in window) memory

from collections import deque

class HitCounter:
    def __init__(self, window=300):
        self.window = window
        self.hits = deque()         # (timestamp, count) buckets per second

    def hit(self, timestamp):
        if self.hits and self.hits[-1][0] == timestamp:
            t, c = self.hits.pop()
            self.hits.append((t, c + 1))   # same second -> bump count
        else:
            self.hits.append((timestamp, 1))

    def get_hits(self, timestamp):
        while self.hits and self.hits[0][0] <= timestamp - self.window:
            self.hits.popleft()            # drop buckets older than window
        return sum(c for _, c in self.hits)
    # bounded to <= window buckets -> O(window) get, O(1) hit

from collections import defaultdict
import heapq

class Comment:
    def __init__(self, cid, parent_id, text, score=0):
        self.id = cid
        self.parent_id = parent_id
        self.text = text
        self.score = score          # proxy for ranking (use Wilson LB in prod)
        self.children = []

def build_comment_tree(rows):
    """rows: list of (id, parent_id, text, score). Returns list of roots."""
    nodes = {r[0]: Comment(*r) for r in rows}
    roots = []
    for c in nodes.values():
        if c.parent_id is None:
            roots.append(c)
        else:
            nodes[c.parent_id].children.append(c)
    return roots

def render(roots, depth=0, out=None):
    """DFS render, siblings ordered best-first (highest score first)."""
    if out is None:
        out = []
    for c in sorted(roots, key=lambda n: -n.score):   # best-first ordering
        out.append("  " * depth + f"[{c.score}] {c.text}")
        render(c.children, depth + 1, out)             # recurse into replies
    return out

# Best-first traversal across the WHOLE thread using a max-heap
def best_first_order(roots):
    """Yield comments globally by score, expanding children lazily."""
    heap = [(-c.score, i, c) for i, c in enumerate(roots)]
    heapq.heapify(heap)
    order = []
    counter = len(roots)
    while heap:
        _, _, c = heapq.heappop(heap)
        order.append(c)
        for child in c.children:
            heapq.heappush(heap, (-child.score, counter, child))
            counter += 1
    return order

class TrieNode:
    def __init__(self):
        self.children = {}          # char -> TrieNode
        self.is_word = False
        self.freq = 0               # for top-k autocomplete

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

    def insert(self, word, freq=1):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
        node.freq += freq

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node                 # subtree rooted at the prefix

    def search(self, word):         # LC 208 exact match
        node = self._find(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):  # LC 208 prefix existence
        return self._find(prefix) is not None

    def autocomplete(self, prefix, k):
        node = self._find(prefix)
        if not node:
            return []
        results = []                # (freq, word) collected via DFS
        def dfs(n, path):
            if n.is_word:
                results.append((n.freq, prefix + path))
            for ch, child in n.children.items():
                dfs(child, path + ch)
        dfs(node, "")
        results.sort(reverse=True)  # by freq desc
        return [w for _, w in results[:k]]

# LC 211: add '.' wildcard search -> DFS over children when '.' seen
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return node.is_word
            ch = word[i]
            if ch == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            return ch in node.children and dfs(node.children[ch], i + 1)
        return dfs(self.root, 0)

# LC 56: merge overlapping intervals
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # overlap -> extend
        else:
            merged.append([start, end])
    return merged                   # O(n log n)

# LC 57: insert a new interval into a sorted, non-overlapping list
def insert_interval(intervals, new):
    res = []
    i, n = 0, len(intervals)
    # 1) intervals strictly before new
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i]); i += 1
    # 2) merge all overlapping with new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    res.append(new)
    # 3) the rest
    while i < n:
        res.append(intervals[i]); i += 1
    return res                      # O(n)

The ~40-problem grid (grouped by pattern)

Do-these-in-this-order plan

Phone-screen simulation checklist