How do you solve `IPO` (`LeetCode 502`, maximizing capital by picking at most $k$ projects) or `Maximum Performance of a Team` (`LC 1383`) using Sorting + Heap?

Whenever a problem optimizes over two attributes `(requirement/threshold, profit/value)`, **sort by one attribute to establish monotonicity, and use a Heap to greedily maintain the best choices on the second attribute**! In `IPO` (`LC 502`): Sort all projects by `capital` required ascending. In each of $k$ rounds, push all projects whose `capital <= current_W` into a **Max-Heap** keyed by `profit`, then pop the single highest-profit project from the Max-Heap and add its profit to `current_W` in $O(n \log n)$ total time.

How do you solve `Unique Paths` (`LC 62`), `Unique Paths II` with Obstacles (`LC 63`), and `Minimum Path Sum` (`LC 64`) on an $M \times N$ grid in $O(N)$ auxiliary space?

Because cell `(r, c)` only depends on the cell directly above `(r - 1, c)` and the cell directly to the left `(r, c - 1)`, you only need a single 1D array `dp` of length $N$! As you iterate `c` from `0` to `N - 1` across row `r`: `dp[c]` before overwriting IS the value from `(r - 1, c)` (above), while `dp[c - 1]` (already updated in this loop) IS the value from `(r, c - 1)` (left)—so `dp[c] = dp[c] + dp[c - 1]` (or `0` if `grid[r][c] == 1` obstacle) in $O(M \cdot N)$ time and $O(N)$ space.

Compare Expand-Around-Center ($O(n^2)$ time, $O(1)$ space) and Manacher's Algorithm ($O(n)$ time) for `Longest Palindromic Substring` (`LeetCode 5`) and `Palindromic Substrings` (`LC 647`).

Expand-Around-Center: A palindrome of length $n$ has $2n - 1$ possible centers ($n$ single-character centers `(i, i)` for odd-length palindromes, and $n - 1$ between-character centers `(i, i + 1)` for even-length palindromes). Expanding outward from each center while `s[L] == s[R]` takes $O(n^2)$ worst-case time and $O(1)$ space. Manacher's Algorithm inserts `'#'` sentinels (`#a#b#a#`) so all palindromes become odd-length, and reuses previously computed palindrome radii mirrored across the rightmost palindrome's center `C` (`P[i] = min(R - i, P[2*C - i])`), achieving strict $O(n)$ linear time.

What is Digit DP (e.g., `Count Numbers with Unique Digits`, `Numbers At Most N Given Digit Set` `LC 902`, `Number of Digit One` `LC 233`)?

Digit DP counts how many integers in $[0, R]$ satisfy a digit property by building the number digit-by-digit from Most Significant Digit to Least Significant Digit (`idx` from `0` to `len(str(R)) - 1`). Memoize state `dfs(idx, is_tight, is_started, state)`: when `is_tight` is `True`, the current digit `d` is restricted to `0 .. int(R[idx])` (and `next_tight = (d == int(R[idx]))`); once a strictly smaller digit is chosen (`d < int(R[idx])`), `is_tight` becomes `False` and all remaining positions can freely choose `0 .. 9`!

Why do you sort by **END time** for `Non-overlapping Intervals` (`LeetCode 435`) and `Min Arrows to Burst Balloons` (`LC 452`), whereas you sort by **START time** for `Merge Intervals` (`LC 56`)?

When selecting the maximum number of mutually compatible (non-overlapping) intervals (`Interval Scheduling` / `LC 435` / `LC 452`), sorting by **earliest END time** (`key=lambda x: x[1]`) is optimal because finishing as early as possible leaves the maximum possible remaining timeline for future intervals! By contrast, `Merge Intervals` (`LC 56`) combines all transitively overlapping intervals into contiguous blocks, which requires processing intervals in increasing order of **START time** (`key=lambda x: x[0]`).

What is the Greedy Choice Property, and how do you prove a Greedy Algorithm is optimal (Exchange Argument vs. Stays-Ahead)?

A problem has the **Greedy Choice Property** if a globally optimal solution can always be reached by making a locally optimal choice at each step without reconsidering past choices. 1. **Exchange Argument**: Assume an arbitrary optimal solution $O$ differs from the greedy solution $G$; show that swapping one element in $O$ for the greedy choice produces a valid solution $O'$ that is no worse than $O$. 2. **Greedy Stays Ahead**: Prove by induction that after step $k$, the greedy partial solution is at least as good as any other solution's step $k$.

Compare the recursion tree structures and complexities of `Subsets` (`LC 78`), `Combinations` (`LC 77`), and `Permutations` (`LC 46`).

1. `Subsets`: $2^n$ subsets; either binary choice (`include i` vs `exclude i`) or loop `for j in range(start, n)` advancing `backtrack(j + 1)`—time $O(n \cdot 2^n)$. 2. `Combinations` ($\binom{n}{k}$): Same `for j in range(start, n)` loop, plus **length pruning**: stop looping when remaining elements `n - j < k - len(path)`! 3. `Permutations`: $n!$ orderings; every index can appear at any position, so loop `for j in range(n)` using a `used` boolean array (or swap `nums[idx]` with `nums[j]` in-place)—time $O(n \cdot n!)$.

How does the Two-Pass Greedy approach solve `Candy` (`LeetCode 135`) and `Partition Labels` (`LeetCode 763`) in $O(n)$ time?

`Candy` (`LC 135`): Initialize `candies = [1] * n`. Pass 1 (Left-to-Right): enforce left neighbor rule `if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1`. Pass 2 (Right-to-Left): enforce right neighbor rule `if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1)`. `Partition Labels` (`LC 763`): Pass 1 records `last[ch] = i` for each character; Pass 2 maintains `end = max(end, last[ch])` and cuts a partition whenever `i == end`!

What two mathematical properties must a problem have to be solvable by Dynamic Programming, and how do Top-Down (Memoization) and Bottom-Up (Tabulation) compare?

1. **Optimal Substructure** (an optimal solution to the problem can be constructed from optimal solutions of its subproblems); and 2. **Overlapping Subproblems** (recursive exploration solves the exact same subproblems repeatedly). Top-Down (`@functools.lru_cache(None)`): Natural recursive formulation that only computes reachable states, but incurs recursion call-stack overhead ($O(H)$ stack space). Bottom-Up (Tabulation): Iteratively fills a table in topological order of states with zero recursion overhead and allows **Space Optimization** (rolling rows, e.g., $O(N \cdot W) \to O(W)$).

How do you solve `Jump Game` (`LeetCode 55`) and `Jump Game II` (Minimum Jumps, `LeetCode 45`) in $O(n)$ greedy time and $O(1)$ space?

`Jump Game I` (`LC 55`): Track `max_reach = 0`; for `i, jump` in `enumerate(nums)`: `if i > max_reach: return False`; `max_reach = max(max_reach, i + jump)`—returns `True`. `Jump Game II` (`LC 45`, implicit 1D BFS levels in $O(1)$ space): Track current jump's boundary `curr_end = 0`, `farthest = 0`, and `jumps = 0`. For `i` in `range(n - 1)`: update `farthest = max(farthest, i + nums[i])`; whenever `i == curr_end`, we must take a jump: `jumps += 1; curr_end = farthest`.

Explain the universal Finite State Machine DP for all six `Best Time to Buy and Sell Stock` problems (`Cooldown` `LC 309`, `Transaction Fee` `LC 714`, `At Most K Transactions` `LC 188`).

At each day, track two states: `cash` (max profit holding 0 stock) and `hold` (max profit holding 1 share of stock, initialized to `-inf`). With Transaction Fee (`LC 714`): `cash, hold = max(cash, hold + price - fee), max(hold, cash - price)`. With 1-Day Cooldown (`LC 309`): add `prev_cash` (cash from 2 days ago) so buying uses `prev_cash - price`. With at most $K$ transactions (`LC 188`): maintain arrays `cash[1..K]` and `hold[1..K]` updated in $O(n \cdot K)$ time and $O(K)$ space.

How does 2D DP handle the `'*'` wildcard in `Regular Expression Matching` (`LeetCode 10`) vs. `Wildcard Matching` (`LeetCode 44`)?

1. In `Wildcard Matching` (`LC 44`), `'*'` is a standalone wildcard matching ANY sequence of 0 or more characters: when `p[j-1] == '*'`, `dp[i][j] = dp[i][j-1]` (match 0 chars) `or dp[i-1][j]` (consume 1 char `s[i-1]` and keep `'*'` active). 2. In `Regex Matching` (`LC 10`), `'*'` modifies the **preceding element** `p[j-2]` (zero or more of `p[j-2]`): when `p[j-1] == '*'`, `dp[i][j] = dp[i][j-2]` (zero occurrences of `p[j-2]*`) `or (matches(s[i-1], p[j-2]) and dp[i-1][j])`.

What is the Meet-in-the-Middle algorithm (`Partition Array Into Two Arrays to Minimize Sum Difference` `LC 2035`, `Closest Subsequence Sum` `LC 1755`) when $N = 40$ and values are too large for pseudo-polynomial DP?

When $N = 40$ (so $2^{40} \approx 10^{12}$ TLEs for brute force) and array values are up to $10^9$ (so Knapsack DP table size is impossible): split the array into two halves `left` and `right` of size $N/2 = 20$ each! Generate all $2^{20} \approx 10^6$ subset sums of `left` and all $2^{20} \approx 10^6$ subset sums of `right`, sort the `right` sums, and for each sum `s_L` in `left`, binary search (`bisect_left`) in `right` for `target - s_L`—reducing complexity from $O(2^{40})$ to $O(2^{N/2} \cdot (N/2)) \approx 2 \times 10^7$ operations!

State the recurrence relation and space optimization for `Longest Common Subsequence` (LCS, `LeetCode 1143`) of strings `s1` ($m$) and `s2` ($n$).

If `s1[i] == s2[j]`, then `dp[i + 1][j + 1] = 1 + dp[i][j]`; otherwise (`s1[i] != s2[j]`), `dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])`. Runs in $O(m \cdot n)$ time. Since row `i + 1` only depends on row `i` and row `i + 1`, we can optimize space to a single 1D row of length $\min(m, n) + 1$ ($O(\min(m, n))$ auxiliary space).

In `Russian Doll Envelopes` (`LeetCode 354`, 2D LIS on `(width, height)`), why do we sort by `width` ASCENDING and `height` DESCENDING on ties?

Because an envelope `(w1, h1)` can only fit inside `(w2, h2)` if BOTH $w_1 < w_2$ AND $h_1 < h_2$ (strict inequalities). Sorting by `width` ascending reduces the problem to 1D LIS on `height`. However, if two envelopes share the same width (e.g., `(3, 4)` and `(3, 5)`), sorting `height` ascending would allow the 1D LIS on `heights` (`[4, 5]`) to illegally pick both! Sorting `height` **descending** on width ties (`(3, 5)` before `(3, 4)`) guarantees at most one envelope per distinct width can ever be picked in a strictly increasing height subsequence!

Explain the crucial inner-loop direction difference between 1D Space-Optimized **0/1 Knapsack** (`Partition Equal Subset Sum` `LC 416`) and **Unbounded Knapsack** (`Coin Change` `LC 322`).

In **0/1 Knapsack** (each item can be used **at most ONCE**), the inner capacity loop MUST iterate **BACKWARDS** (`for w in range(W, weight - 1, -1): dp[w] = max(dp[w], dp[w - weight] + val)`) so that `dp[w - weight]` still holds the value from the *previous* item's row (`i - 1`), preventing the same item from being picked multiple times! In **Unbounded Knapsack** (each item/coin can be reused **UNLIMITED times**), the inner loop iterates **FORWARDS** (`for w in range(weight, W + 1): ...`) so `dp[w - weight]` intentionally reuses the *current* item (`i`).

How do you solve `House Robber` (`LeetCode 198`), `House Robber II` (Circular, `LC 213`), and `House Robber III` (Binary Tree, `LC 337`)?

`House Robber I` (1D): `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`, optimized to two variables `prev2, prev1 = prev1, max(prev1, prev2 + x)` in $O(n)$ time, $O(1)$ space. `House Robber II` (Circular): Since house `0` and `n-1` are adjacent, you cannot rob both—take `max(rob_linear(nums[:-1]), rob_linear(nums[1:]))`. `House Robber III` (Tree DP): Post-order `dfs(node)` returns a 2-tuple `(rob_this_node, skip_this_node)` where `rob = node.val + L.skip + R.skip` and `skip = max(L) + max(R)` in $O(n)$ time.

How do you solve `Generate Parentheses` (`LeetCode 22`) using constrained backtracking, and what sequence gives the exact count of outputs?

Track `(open_count, close_count)`: 1. You can add `'('` whenever `open_count < n`; 2. You can add `')'` ONLY when `close_count < open_count` (which guarantees no prefix ever has more `')'` than `'('`, pruning 100% of invalid strings before they are even built!). The number of valid strings of $n$ pairs is the $n$-th **Catalan Number** $C_n = \frac{1}{n + 1}\binom{2n}{n} = \Theta\left(\frac{4^n}{n^{3/2}}\right)$ (which also counts unique BSTs with $n$ nodes in `LeetCode 96`!).

Why does the loop order (`coins` outer vs. `amount` outer) change the answer between `Coin Change II` (Combinations, `LeetCode 518`) and `Combination Sum IV` (Permutations, `LeetCode 377`)?

1. **Combinations** (order does NOT matter, so `1+2` and `2+1` count as 1 way, `LC 518`): Put **`for coin in coins:` on the OUTER loop** and `for a in range(coin, amount + 1): dp[a] += dp[a - coin]` on the INNER loop—this forces coins to be used in canonical order (`coin_1`s then `coin_2`s). 2. **Permutations** (order DOES matter, so `1+2` and `2+1` count as 2 ways, `LC 377`): Put **`for a in range(1, amount + 1):` on the OUTER loop** and `for coin in coins:` on the INNER loop!

How does Huffman Coding construct an optimal prefix-free binary code using a Greedy Min-Heap?

To minimize weighted path length $\sum f_i \cdot \text{depth}(c_i)$ without any codeword being a prefix of another (Prefix-Free property, achieved by placing all characters at leaf nodes): push all `(freq, char)` nodes into a Min-Heap. While `len(heap) > 1`: pop the TWO lowest-frequency nodes `left` and `right`, combine them under a new internal parent node with `freq = left.freq + right.freq`, and push the parent back into the Min-Heap ($O(n \log n)$ time).

Why does a Greedy algorithm work for US Coin denominations `[1, 5, 10, 25]` (`Canonical Coin Systems`), yet fail for general `Coin Change` (`LeetCode 322`)?

For arbitrary coin sets like `coins = [1, 3, 4]` and `amount = 6`, the Greedy choice picks the largest coin `4` first, forcing `4 + 1 + 1` (`3` coins), whereas the true optimal solution is `3 + 3` (`2` coins)! Because earlier greedy choices constrain future divisibility in non-canonical coin systems, general `Coin Change` lacks the Greedy Choice Property and requires $O(n \cdot \text{amount})$ Dynamic Programming (or BFS for unweighted shortest steps).

Explain the $O(n)$ greedy invariant behind `Gas Station` (`LeetCode 134`).

Two key observations: 1. If `sum(gas) = sum(cost)`, a unique valid starting station is guaranteed to exist! 2. Maintain a running `tank = 0` and candidate `start = 0`. If `tank + gas[i] - cost[i] < 0` at station `i`, then **NO station between `start` and `i` inclusive can be the valid starting point** (because `start` entered every intermediate station with a non-negative tank surplus $\ge 0$ and still ran dry at `i`!), so immediately reset `start = i + 1` and `tank = 0`.

How do you eliminate duplicate outputs in `Subsets II` (`LC 90`), `Combination Sum II` (`LC 40`), and `Permutations II` (`LC 47`) when the input contains duplicate numbers?

**Sort `nums` first** so identical values are adjacent! 1. In `Subsets II` (`LC 90`) and `Combination Sum II` (`LC 40`), inside `for j in range(start, n):`, skip choosing the same value twice at the **same recursion tree depth**: `if j > start and nums[j] == nums[j - 1]: continue`! 2. In `Permutations II` (`LC 47`), inside `for j in range(n):`, skip `if used[j] or (j > 0 and nums[j] == nums[j - 1] and not used[j - 1]): continue` (which forces identical numbers to be used strictly in left-to-right order).

How do you reduce `Target Sum` (assigning `+` or `-` to every number in `nums` to reach `target`, `LeetCode 494`) to a 1D 0/1 Subset Sum DP?

Partition `nums` into positive subset $P$ and negative subset $N$. We know $\sum P - \sum N = \text{target}$ and $\sum P + \sum N = \text{total\_sum}$. Adding the two equations gives $2 \sum P = \text{target} + \text{total\_sum} \implies \sum P = \frac{\text{target} + \text{total\_sum}}{2}$. If $\text{target} + \text{total\_sum}$ is odd or $< 0$, return `0`; otherwise count the number of subsets of `nums` that sum to $S = (\text{target} + \text{total\_sum}) // 2$ using 1D backwards 0/1 Knapsack in $O(n \cdot S)$ time and $O(S)$ space!

How do you solve `Word Break` (`LeetCode 139`) and `Decode Ways` (`LeetCode 91`) using 1D Prefix DP?

`Word Break` (`LC 139`): Convert `wordDict` to a Hash Set (and record `max_word_len`). Define `dp[i]` = True if prefix `s[0:i]` can be segmented (`dp[0] = True`). For `i` from `1` to `n`: check `j` from `max(0, i - max_word_len)` to `i - 1`—if `dp[j] and s[j:i] in word_set: dp[i] = True; break`. `Decode Ways` (`LC 91`): `dp[i]` = ways to decode up to index `i`; add `dp[i-1]` if `s[i-1] != '0'`, and add `dp[i-2]` if `10 <= int(s[i-2:i]) <= 26` ($O(n)$ time, $O(1)$ space).

How do you solve `Maximum Subarray` variants with state transitions like `Maximum Product Subarray` (`LeetCode 152`) in $O(n)$ time and $O(1)$ space?

Unlike sum, multiplying a very negative number by another negative number flips it into a huge positive number! Therefore, at each element `x`, track BOTH `cur_max` and `cur_min` ending at index `i`: `candidates = (x, x * cur_max, x * cur_min)`; update `cur_max, cur_min = max(candidates), min(candidates)` simultaneously, and `best = max(best, cur_max)` in $O(n)$ time and $O(1)$ space.

How do you solve `Longest Increasing Subsequence` (LIS, `LeetCode 300`) in $O(n \log n)$ time instead of $O(n^2)$ DP using Patience Sorting + Binary Search?

Maintain a strictly increasing array `tails`, where `tails[k]` stores the **smallest possible tail element** of any increasing subsequence of length `k + 1` seen so far. For each `x` in `nums`: find insertion index `idx = bisect_left(tails, x)` (use `bisect_right` for non-decreasing subsequence). If `idx == len(tails)`, append `x` to `tails`; otherwise overwrite `tails[idx] = x` (keeping the tail of length `idx + 1` as small as possible to accommodate more future elements!). At the end, `len(tails)` is the exact LIS length in $O(n \log n)$ time!

How do you represent board constraints in `N-Queens` (`LeetCode 51`) and `Sudoku Solver` (`LeetCode 37`) to check validity in $O(1)$ time?

In `N-Queens` (`LC 51`), placing one queen per row `r` from `0` to `n - 1` automatically prevents row conflicts. Track occupied columns and diagonals using three Hash Sets or Bitmasks: 1. `cols` (`c`); 2. `diag1` (`r - c`, constant along top-left to bottom-right diagonals); and 3. `diag2` (`r + c`, constant along bottom-left to top-right anti-diagonals)! In `Sudoku Solver` (`LC 37`), maintain 9 bitmasks each for `rows[r]`, `cols[c]`, and `boxes[(r // 3) * 3 + (c // 3)]`, testing digit `d` in $O(1)$ via bitwise AND.

State the recurrence relation for Levenshtein `Edit Distance` (`LeetCode 72`) converting `word1` into `word2` using Insert, Delete, and Replace.

Base cases: `dp[i][0] = i` (delete $i$ chars) and `dp[0][j] = j` (insert $j$ chars). For $i, j \ge 1$: if `word1[i - 1] == word2[j - 1]`, no operation is needed: `dp[i][j] = dp[i - 1][j - 1]`. Otherwise, take $1 + \min($ `dp[i - 1][j]` (Delete from `word1`), `dp[i][j - 1]` (Insert into `word1`), `dp[i - 1][j - 1]` (Replace char)$)$ in $O(m \cdot n)$ time and $O(\min(m, n))$ optimized space.

What is the universal Backtracking template (`Choose -> Explore -> Unchoose`) and how do you avoid $O(n)$ array copies at every recursive step?

Maintain a single shared mutable `path = []` list across the recursion tree. Inside `backtrack(start_idx)`: 1. If base case reached, append a shallow copy `res.append(path[:])` (ONLY copy when recording a completed answer); 2. Loop over candidate choices: (a) **Choose**: `path.append(choice)` (and update visited/state in $O(1)$); (b) **Explore**: `backtrack(next_idx)`; (c) **Unchoose (Backtrack)**: `path.pop()` (and restore visited/state in $O(1)$).

Explain the Interval DP pattern and why you must iterate by **interval length `len` from 1 to $n$** (e.g., `Burst Balloons` `LC 312`, `Longest Palindromic Subsequence` `LC 516`).

In Interval DP, state `dp[i][j]` represents the optimal answer for subarray `s[i..j]`, which depends on smaller sub-intervals inside `[i..j]` (`dp[i+1][j]`, `dp[i][j-1]`, or `dp[i][k] + dp[k+1][j]`). Therefore, you must loop outer over `length` from `2` to `n` (or loop `i` backwards from `n-1` down to `0` and `j` forwards from `i+1` to `n-1`). In `Burst Balloons` (`LC 312`), instead of picking which balloon in `(i, j)` to burst *first* (which makes adjacent neighbors change dynamically!), pick which balloon `k` in `(i, j)` is burst **LAST**—so its neighbors at burst time are guaranteed to be the fixed boundaries `nums[i]` and `nums[j]`!

Explain Bitmask Dynamic Programming (`Traveling Salesperson Problem`, `Shortest Path Visiting All Nodes` `LC 847`, `Campus Bikes II` `LC 1066`).

When $N \le 20$ and you need to track which subset of $N$ items has been visited/assigned, represent the subset as an $N$-bit integer `mask` from `0` to `(1 > i) & 1`). Adding item $i$ transitions to `next_mask = mask | (1 << i)`. For TSP, state `dp[mask][u]` is the min cost to visit the subset `mask` ending at vertex `u`, reducing complexity from $O(N!)$ brute-force permutations to $O(N^2 \cdot 2^N)$!

Dynamic Programming, Backtracking & Greedy Algorithm Patterns

Intermediate-to-advanced algorithmic problem solving covering Top-Down Memoization vs Bottom-Up Tabulation, 0/1 and Unbounded Knapsack, Coin Change, LCS, Edit Distance, O(n log n) LIS (Patience Sorting), Manacher's Palindrome algorithm, Interval DP, Bitmask DP, Backtracking pruning templates, and Greedy proofs.

Level: intermediate
Languages: en → en
Cards: 32
Markdown: Dynamic Programming, Backtracking & Greedy Algorithm Patterns (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	How do you solve `IPO` (`LeetCode 502`, maximizing capital by picking at most $k$ projects) or `Maximum Performance of a Team` (`LC 1383`) using Sorting + Heap?	Whenever a problem optimizes over two attributes `(requirement/threshold, profit/value)`, sort by one attribute to establish monotonicity, and use a Heap to greedily maintain the best choices on the second attribute! In `IPO` (`LC 502`): Sort all projects by `capital` required ascending. In each of $k$ rounds, push all projects whose `capital <= current_W` into a Max-Heap keyed by `profit`, then pop the single highest-profit project from the Max-Heap and add its profit to `current_W` in $O(n \log n)$ total time.
2	How do you solve `Unique Paths` (`LC 62`), `Unique Paths II` with Obstacles (`LC 63`), and `Minimum Path Sum` (`LC 64`) on an $M \times N$ grid in $O(N)$ auxiliary space?	Because cell `(r, c)` only depends on the cell directly above `(r - 1, c)` and the cell directly to the left `(r, c - 1)`, you only need a single 1D array `dp` of length $N$! As you iterate `c` from `0` to `N - 1` across row `r`: `dp[c]` before overwriting IS the value from `(r - 1, c)` (above), while `dp[c - 1]` (already updated in this loop) IS the value from `(r, c - 1)` (left)—so `dp[c] = dp[c] + dp[c - 1]` (or `0` if `grid[r][c] == 1` obstacle) in $O(M \cdot N)$ time and $O(N)$ space.
3	Compare Expand-Around-Center ($O(n^2)$ time, $O(1)$ space) and Manacher's Algorithm ($O(n)$ time) for `Longest Palindromic Substring` (`LeetCode 5`) and `Palindromic Substrings` (`LC 647`).	Expand-Around-Center: A palindrome of length $n$ has $2n - 1$ possible centers ($n$ single-character centers `(i, i)` for odd-length palindromes, and $n - 1$ between-character centers `(i, i + 1)` for even-length palindromes). Expanding outward from each center while `s[L] == s[R]` takes $O(n^2)$ worst-case time and $O(1)$ space. Manacher's Algorithm inserts `'#'` sentinels (`#a#b#a#`) so all palindromes become odd-length, and reuses previously computed palindrome radii mirrored across the rightmost palindrome's center `C` (`P[i] = min(R - i, P[2*C - i])`), achieving strict $O(n)$ linear time.
4	What is Digit DP (e.g., `Count Numbers with Unique Digits`, `Numbers At Most N Given Digit Set` `LC 902`, `Number of Digit One` `LC 233`)?	Digit DP counts how many integers in $[0, R]$ satisfy a digit property by building the number digit-by-digit from Most Significant Digit to Least Significant Digit (`idx` from `0` to `len(str(R)) - 1`). Memoize state `dfs(idx, is_tight, is_started, state)`: when `is_tight` is `True`, the current digit `d` is restricted to `0 .. int(R[idx])` (and `next_tight = (d == int(R[idx]))`); once a strictly smaller digit is chosen (`d < int(R[idx])`), `is_tight` becomes `False` and all remaining positions can freely choose `0 .. 9`!
5	Why do you sort by END time for `Non-overlapping Intervals` (`LeetCode 435`) and `Min Arrows to Burst Balloons` (`LC 452`), whereas you sort by START time for `Merge Intervals` (`LC 56`)?	When selecting the maximum number of mutually compatible (non-overlapping) intervals (`Interval Scheduling` / `LC 435` / `LC 452`), sorting by earliest END time (`key=lambda x: x[1]`) is optimal because finishing as early as possible leaves the maximum possible remaining timeline for future intervals! By contrast, `Merge Intervals` (`LC 56`) combines all transitively overlapping intervals into contiguous blocks, which requires processing intervals in increasing order of START time (`key=lambda x: x[0]`).
6	What is the Greedy Choice Property, and how do you prove a Greedy Algorithm is optimal (Exchange Argument vs. Stays-Ahead)?	A problem has the Greedy Choice Property if a globally optimal solution can always be reached by making a locally optimal choice at each step without reconsidering past choices. 1. Exchange Argument: Assume an arbitrary optimal solution $O$ differs from the greedy solution $G$; show that swapping one element in $O$ for the greedy choice produces a valid solution $O'$ that is no worse than $O$. 2. Greedy Stays Ahead: Prove by induction that after step $k$, the greedy partial solution is at least as good as any other solution's step $k$.
7	Compare the recursion tree structures and complexities of `Subsets` (`LC 78`), `Combinations` (`LC 77`), and `Permutations` (`LC 46`).	1. `Subsets`: $2^n$ subsets; either binary choice (`include i` vs `exclude i`) or loop `for j in range(start, n)` advancing `backtrack(j + 1)`—time $O(n \cdot 2^n)$. 2. `Combinations` ($\binom{n}{k}$): Same `for j in range(start, n)` loop, plus length pruning: stop looping when remaining elements `n - j < k - len(path)`! 3. `Permutations`: $n!$ orderings; every index can appear at any position, so loop `for j in range(n)` using a `used` boolean array (or swap `nums[idx]` with `nums[j]` in-place)—time $O(n \cdot n!)$.
8	How does the Two-Pass Greedy approach solve `Candy` (`LeetCode 135`) and `Partition Labels` (`LeetCode 763`) in $O(n)$ time?	`Candy` (`LC 135`): Initialize `candies = [1] * n`. Pass 1 (Left-to-Right): enforce left neighbor rule `if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1`. Pass 2 (Right-to-Left): enforce right neighbor rule `if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1)`. `Partition Labels` (`LC 763`): Pass 1 records `last[ch] = i` for each character; Pass 2 maintains `end = max(end, last[ch])` and cuts a partition whenever `i == end`!
9	What two mathematical properties must a problem have to be solvable by Dynamic Programming, and how do Top-Down (Memoization) and Bottom-Up (Tabulation) compare?	1. Optimal Substructure (an optimal solution to the problem can be constructed from optimal solutions of its subproblems); and 2. Overlapping Subproblems (recursive exploration solves the exact same subproblems repeatedly). Top-Down (`@functools.lru_cache(None)`): Natural recursive formulation that only computes reachable states, but incurs recursion call-stack overhead ($O(H)$ stack space). Bottom-Up (Tabulation): Iteratively fills a table in topological order of states with zero recursion overhead and allows Space Optimization (rolling rows, e.g., $O(N \cdot W) \to O(W)$).
10	How do you solve `Jump Game` (`LeetCode 55`) and `Jump Game II` (Minimum Jumps, `LeetCode 45`) in $O(n)$ greedy time and $O(1)$ space?	`Jump Game I` (`LC 55`): Track `max_reach = 0`; for `i, jump` in `enumerate(nums)`: `if i > max_reach: return False`; `max_reach = max(max_reach, i + jump)`—returns `True`. `Jump Game II` (`LC 45`, implicit 1D BFS levels in $O(1)$ space): Track current jump's boundary `curr_end = 0`, `farthest = 0`, and `jumps = 0`. For `i` in `range(n - 1)`: update `farthest = max(farthest, i + nums[i])`; whenever `i == curr_end`, we must take a jump: `jumps += 1; curr_end = farthest`.
11	Explain the universal Finite State Machine DP for all six `Best Time to Buy and Sell Stock` problems (`Cooldown` `LC 309`, `Transaction Fee` `LC 714`, `At Most K Transactions` `LC 188`).	At each day, track two states: `cash` (max profit holding 0 stock) and `hold` (max profit holding 1 share of stock, initialized to `-inf`). With Transaction Fee (`LC 714`): `cash, hold = max(cash, hold + price - fee), max(hold, cash - price)`. With 1-Day Cooldown (`LC 309`): add `prev_cash` (cash from 2 days ago) so buying uses `prev_cash - price`. With at most $K$ transactions (`LC 188`): maintain arrays `cash[1..K]` and `hold[1..K]` updated in $O(n \cdot K)$ time and $O(K)$ space.
12	How does 2D DP handle the `'*'` wildcard in `Regular Expression Matching` (`LeetCode 10`) vs. `Wildcard Matching` (`LeetCode 44`)?	1. In `Wildcard Matching` (`LC 44`), `''` is a standalone wildcard matching ANY sequence of 0 or more characters: when `p[j-1] == ''`, `dp[i][j] = dp[i][j-1]` (match 0 chars) `or dp[i-1][j]` (consume 1 char `s[i-1]` and keep `''` active). 2. In `Regex Matching` (`LC 10`), `''` modifies the preceding element `p[j-2]` (zero or more of `p[j-2]`): when `p[j-1] == ''`, `dp[i][j] = dp[i][j-2]` (zero occurrences of `p[j-2]`) `or (matches(s[i-1], p[j-2]) and dp[i-1][j])`.
13	What is the Meet-in-the-Middle algorithm (`Partition Array Into Two Arrays to Minimize Sum Difference` `LC 2035`, `Closest Subsequence Sum` `LC 1755`) when $N = 40$ and values are too large for pseudo-polynomial DP?	When $N = 40$ (so $2^{40} \approx 10^{12}$ TLEs for brute force) and array values are up to $10^9$ (so Knapsack DP table size is impossible): split the array into two halves `left` and `right` of size $N/2 = 20$ each! Generate all $2^{20} \approx 10^6$ subset sums of `left` and all $2^{20} \approx 10^6$ subset sums of `right`, sort the `right` sums, and for each sum `s_L` in `left`, binary search (`bisect_left`) in `right` for `target - s_L`—reducing complexity from $O(2^{40})$ to $O(2^{N/2} \cdot (N/2)) \approx 2 \times 10^7$ operations!
14	State the recurrence relation and space optimization for `Longest Common Subsequence` (LCS, `LeetCode 1143`) of strings `s1` ($m$) and `s2` ($n$).	If `s1[i] == s2[j]`, then `dp[i + 1][j + 1] = 1 + dp[i][j]`; otherwise (`s1[i] != s2[j]`), `dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])`. Runs in $O(m \cdot n)$ time. Since row `i + 1` only depends on row `i` and row `i + 1`, we can optimize space to a single 1D row of length $\min(m, n) + 1$ ($O(\min(m, n))$ auxiliary space).
15	In `Russian Doll Envelopes` (`LeetCode 354`, 2D LIS on `(width, height)`), why do we sort by `width` ASCENDING and `height` DESCENDING on ties?	Because an envelope `(w1, h1)` can only fit inside `(w2, h2)` if BOTH $w_1 < w_2$ AND $h_1 < h_2$ (strict inequalities). Sorting by `width` ascending reduces the problem to 1D LIS on `height`. However, if two envelopes share the same width (e.g., `(3, 4)` and `(3, 5)`), sorting `height` ascending would allow the 1D LIS on `heights` (`[4, 5]`) to illegally pick both! Sorting `height` descending on width ties (`(3, 5)` before `(3, 4)`) guarantees at most one envelope per distinct width can ever be picked in a strictly increasing height subsequence!
16	Explain the crucial inner-loop direction difference between 1D Space-Optimized 0/1 Knapsack (`Partition Equal Subset Sum` `LC 416`) and Unbounded Knapsack (`Coin Change` `LC 322`).	In 0/1 Knapsack (each item can be used at most ONCE), the inner capacity loop MUST iterate BACKWARDS (`for w in range(W, weight - 1, -1): dp[w] = max(dp[w], dp[w - weight] + val)`) so that `dp[w - weight]` still holds the value from the previous item's row (`i - 1`), preventing the same item from being picked multiple times! In Unbounded Knapsack (each item/coin can be reused UNLIMITED times), the inner loop iterates FORWARDS (`for w in range(weight, W + 1): ...`) so `dp[w - weight]` intentionally reuses the current item (`i`).
17	How do you solve `House Robber` (`LeetCode 198`), `House Robber II` (Circular, `LC 213`), and `House Robber III` (Binary Tree, `LC 337`)?	`House Robber I` (1D): `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`, optimized to two variables `prev2, prev1 = prev1, max(prev1, prev2 + x)` in $O(n)$ time, $O(1)$ space. `House Robber II` (Circular): Since house `0` and `n-1` are adjacent, you cannot rob both—take `max(rob_linear(nums[:-1]), rob_linear(nums[1:]))`. `House Robber III` (Tree DP): Post-order `dfs(node)` returns a 2-tuple `(rob_this_node, skip_this_node)` where `rob = node.val + L.skip + R.skip` and `skip = max(L) + max(R)` in $O(n)$ time.
18	How do you solve `Generate Parentheses` (`LeetCode 22`) using constrained backtracking, and what sequence gives the exact count of outputs?	Track `(open_count, close_count)`: 1. You can add `'('` whenever `open_count < n`; 2. You can add `')'` ONLY when `close_count < open_count` (which guarantees no prefix ever has more `')'` than `'('`, pruning 100% of invalid strings before they are even built!). The number of valid strings of $n$ pairs is the $n$-th Catalan Number $C_n = \frac{1}{n + 1}\binom{2n}{n} = \Theta\left(\frac{4^n}{n^{3/2}}\right)$ (which also counts unique BSTs with $n$ nodes in `LeetCode 96`!).
19	Why does the loop order (`coins` outer vs. `amount` outer) change the answer between `Coin Change II` (Combinations, `LeetCode 518`) and `Combination Sum IV` (Permutations, `LeetCode 377`)?	1. Combinations (order does NOT matter, so `1+2` and `2+1` count as 1 way, `LC 518`): Put `for coin in coins:` on the OUTER loop and `for a in range(coin, amount + 1): dp[a] += dp[a - coin]` on the INNER loop—this forces coins to be used in canonical order (`coin_1`s then `coin_2`s). 2. Permutations (order DOES matter, so `1+2` and `2+1` count as 2 ways, `LC 377`): Put `for a in range(1, amount + 1):` on the OUTER loop and `for coin in coins:` on the INNER loop!
20	How does Huffman Coding construct an optimal prefix-free binary code using a Greedy Min-Heap?	To minimize weighted path length $\sum f_i \cdot \text{depth}(c_i)$ without any codeword being a prefix of another (Prefix-Free property, achieved by placing all characters at leaf nodes): push all `(freq, char)` nodes into a Min-Heap. While `len(heap) > 1`: pop the TWO lowest-frequency nodes `left` and `right`, combine them under a new internal parent node with `freq = left.freq + right.freq`, and push the parent back into the Min-Heap ($O(n \log n)$ time).
21	Why does a Greedy algorithm work for US Coin denominations `[1, 5, 10, 25]` (`Canonical Coin Systems`), yet fail for general `Coin Change` (`LeetCode 322`)?	For arbitrary coin sets like `coins = [1, 3, 4]` and `amount = 6`, the Greedy choice picks the largest coin `4` first, forcing `4 + 1 + 1` (`3` coins), whereas the true optimal solution is `3 + 3` (`2` coins)! Because earlier greedy choices constrain future divisibility in non-canonical coin systems, general `Coin Change` lacks the Greedy Choice Property and requires $O(n \cdot \text{amount})$ Dynamic Programming (or BFS for unweighted shortest steps).
22	Explain the $O(n)$ greedy invariant behind `Gas Station` (`LeetCode 134`).	Two key observations: 1. If `sum(gas) < sum(cost)`, no solution can possibly exist—return `-1`; if `sum(gas) >= sum(cost)`, a unique valid starting station is guaranteed to exist! 2. Maintain a running `tank = 0` and candidate `start = 0`. If `tank + gas[i] - cost[i] < 0` at station `i`, then NO station between `start` and `i` inclusive can be the valid starting point (because `start` entered every intermediate station with a non-negative tank surplus $\ge 0$ and still ran dry at `i`!), so immediately reset `start = i + 1` and `tank = 0`.
23	How do you eliminate duplicate outputs in `Subsets II` (`LC 90`), `Combination Sum II` (`LC 40`), and `Permutations II` (`LC 47`) when the input contains duplicate numbers?	Sort `nums` first so identical values are adjacent! 1. In `Subsets II` (`LC 90`) and `Combination Sum II` (`LC 40`), inside `for j in range(start, n):`, skip choosing the same value twice at the same recursion tree depth: `if j > start and nums[j] == nums[j - 1]: continue`! 2. In `Permutations II` (`LC 47`), inside `for j in range(n):`, skip `if used[j] or (j > 0 and nums[j] == nums[j - 1] and not used[j - 1]): continue` (which forces identical numbers to be used strictly in left-to-right order).
24	How do you reduce `Target Sum` (assigning `+` or `-` to every number in `nums` to reach `target`, `LeetCode 494`) to a 1D 0/1 Subset Sum DP?	Partition `nums` into positive subset $P$ and negative subset $N$. We know $\sum P - \sum N = \text{target}$ and $\sum P + \sum N = \text{total\_sum}$. Adding the two equations gives $2 \sum P = \text{target} + \text{total\_sum} \implies \sum P = \frac{\text{target} + \text{total\_sum}}{2}$. If $\text{target} + \text{total\_sum}$ is odd or lt; 0$, return `0`; otherwise count the number of subsets of `nums` that sum to $S = (\text{target} + \text{total\_sum}) // 2$ using 1D backwards 0/1 Knapsack in $O(n \cdot S)$ time and $O(S)$ space!
25	How do you solve `Word Break` (`LeetCode 139`) and `Decode Ways` (`LeetCode 91`) using 1D Prefix DP?	`Word Break` (`LC 139`): Convert `wordDict` to a Hash Set (and record `max_word_len`). Define `dp[i]` = True if prefix `s[0:i]` can be segmented (`dp[0] = True`). For `i` from `1` to `n`: check `j` from `max(0, i - max_word_len)` to `i - 1`—if `dp[j] and s[j:i] in word_set: dp[i] = True; break`. `Decode Ways` (`LC 91`): `dp[i]` = ways to decode up to index `i`; add `dp[i-1]` if `s[i-1] != '0'`, and add `dp[i-2]` if `10 <= int(s[i-2:i]) <= 26` ($O(n)$ time, $O(1)$ space).
26	How do you solve `Maximum Subarray` variants with state transitions like `Maximum Product Subarray` (`LeetCode 152`) in $O(n)$ time and $O(1)$ space?	Unlike sum, multiplying a very negative number by another negative number flips it into a huge positive number! Therefore, at each element `x`, track BOTH `cur_max` and `cur_min` ending at index `i`: `candidates = (x, x * cur_max, x * cur_min)`; update `cur_max, cur_min = max(candidates), min(candidates)` simultaneously, and `best = max(best, cur_max)` in $O(n)$ time and $O(1)$ space.
27	How do you solve `Longest Increasing Subsequence` (LIS, `LeetCode 300`) in $O(n \log n)$ time instead of $O(n^2)$ DP using Patience Sorting + Binary Search?	Maintain a strictly increasing array `tails`, where `tails[k]` stores the smallest possible tail element of any increasing subsequence of length `k + 1` seen so far. For each `x` in `nums`: find insertion index `idx = bisect_left(tails, x)` (use `bisect_right` for non-decreasing subsequence). If `idx == len(tails)`, append `x` to `tails`; otherwise overwrite `tails[idx] = x` (keeping the tail of length `idx + 1` as small as possible to accommodate more future elements!). At the end, `len(tails)` is the exact LIS length in $O(n \log n)$ time!
28	How do you represent board constraints in `N-Queens` (`LeetCode 51`) and `Sudoku Solver` (`LeetCode 37`) to check validity in $O(1)$ time?	In `N-Queens` (`LC 51`), placing one queen per row `r` from `0` to `n - 1` automatically prevents row conflicts. Track occupied columns and diagonals using three Hash Sets or Bitmasks: 1. `cols` (`c`); 2. `diag1` (`r - c`, constant along top-left to bottom-right diagonals); and 3. `diag2` (`r + c`, constant along bottom-left to top-right anti-diagonals)! In `Sudoku Solver` (`LC 37`), maintain 9 bitmasks each for `rows[r]`, `cols[c]`, and `boxes[(r // 3) * 3 + (c // 3)]`, testing digit `d` in $O(1)$ via bitwise AND.
29	State the recurrence relation for Levenshtein `Edit Distance` (`LeetCode 72`) converting `word1` into `word2` using Insert, Delete, and Replace.	Base cases: `dp[i][0] = i` (delete $i$ chars) and `dp[0][j] = j` (insert $j$ chars). For $i, j \ge 1$: if `word1[i - 1] == word2[j - 1]`, no operation is needed: `dp[i][j] = dp[i - 1][j - 1]`. Otherwise, take $1 + \min($ `dp[i - 1][j]` (Delete from `word1`), `dp[i][j - 1]` (Insert into `word1`), `dp[i - 1][j - 1]` (Replace char)$)$ in $O(m \cdot n)$ time and $O(\min(m, n))$ optimized space.
30	What is the universal Backtracking template (`Choose -> Explore -> Unchoose`) and how do you avoid $O(n)$ array copies at every recursive step?	Maintain a single shared mutable `path = []` list across the recursion tree. Inside `backtrack(start_idx)`: 1. If base case reached, append a shallow copy `res.append(path[:])` (ONLY copy when recording a completed answer); 2. Loop over candidate choices: (a) Choose: `path.append(choice)` (and update visited/state in $O(1)$); (b) Explore: `backtrack(next_idx)`; (c) Unchoose (Backtrack): `path.pop()` (and restore visited/state in $O(1)$).
31	Explain the Interval DP pattern and why you must iterate by interval length `len` from 1 to $n$ (e.g., `Burst Balloons` `LC 312`, `Longest Palindromic Subsequence` `LC 516`).	In Interval DP, state `dp[i][j]` represents the optimal answer for subarray `s[i..j]`, which depends on smaller sub-intervals inside `[i..j]` (`dp[i+1][j]`, `dp[i][j-1]`, or `dp[i][k] + dp[k+1][j]`). Therefore, you must loop outer over `length` from `2` to `n` (or loop `i` backwards from `n-1` down to `0` and `j` forwards from `i+1` to `n-1`). In `Burst Balloons` (`LC 312`), instead of picking which balloon in `(i, j)` to burst first (which makes adjacent neighbors change dynamically!), pick which balloon `k` in `(i, j)` is burst LAST—so its neighbors at burst time are guaranteed to be the fixed boundaries `nums[i]` and `nums[j]`!
32	Explain Bitmask Dynamic Programming (`Traveling Salesperson Problem`, `Shortest Path Visiting All Nodes` `LC 847`, `Campus Bikes II` `LC 1066`).	When $N \le 20$ and you need to track which subset of $N$ items has been visited/assigned, represent the subset as an $N$-bit integer `mask` from `0` to `(1 << N) - 1` (where bit $i$ is `1` if item $i$ is included: `(mask >> i) & 1`). Adding item $i$ transitions to `next_mask = mask \| (1 << i)`. For TSP, state `dp[mask][u]` is the min cost to visit the subset `mask` ending at vertex `u`, reducing complexity from $O(N!)$ brute-force permutations to $O(N^2 \cdot 2^N)$!