Neetcode2H3

Cheatsheet Content

1. Count All Valid Pickup and Delivery Options Problem: Given $n$ orders, each with a pickup and delivery, find the number of valid sequences. Approach: Combinatorics/DP. For $n$ orders, we have $2n$ positions. For the first order, we choose 2 positions for $P_1$ and $D_1$. $P_1$ must come before $D_1$. Number of ways to place $P_i$ and $D_i$ for the $i$-th order: $2i-1$ choices for $P_i$, and $i$ choices for $D_i$ (after $P_i$). Formula: $dp[i] = dp[i-1] \times (2i-1) \times i$. Base case: $dp[1] = 1$. MOD = 10**9 + 7 def countOrders(n: int) -> int: dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = (dp[i-1] * (2 * i - 1) * i) % MOD return dp[n] 2. Minimum Number of Removals to Make Mountain Array Problem: Find the minimum removals to make a mountain array (strictly increasing then strictly decreasing). Approach: DP. For each element $nums[i]$, find the Longest Increasing Subsequence (LIS) ending at $i$, and Longest Decreasing Subsequence (LDS) starting at $i$. Steps: Compute $LIS[i]$ for all $i$. Compute $LDS[i]$ for all $i$ (on reversed array, or from right to left). A mountain array with peak $nums[i]$ has length $LIS[i] + LDS[i] - 1$. Max mountain length = $\max(LIS[i] + LDS[i] - 1)$ for $i$ where $LIS[i] > 1$ and $LDS[i] > 1$. Min removals = $N - \text{max\_mountain\_length}$. def minimumMountainRemovals(nums: list[int]) -> int: n = len(nums) lis = [1] * n lds = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: lis[i] = max(lis[i], lis[j] + 1) for i in range(n - 2, -1, -1): for j in range(n - 1, i, -1): if nums[i] > nums[j]: lds[i] = max(lds[i], lds[j] + 1) max_len = 0 for i in range(n): if lis[i] > 1 and lds[i] > 1: max_len = max(max_len, lis[i] + lds[i] - 1) return n - max_len 3. Find the Longest Valid Obstacle Course at Each Position Problem: For each position $i$, find the length of the longest obstacle course ending at $i$ where obstacles are non-decreasing. Approach: Similar to LIS, but with non-decreasing condition. Use a `tail` array to store the smallest tail of all non-decreasing subsequences of a certain length. Algorithm: Initialize `tails = []` and `ans = []`. For each `obstacle` in `obstacles`: Use `bisect_right` to find the insertion point for `obstacle` in `tails`. If `obstacle` is greater than all elements in `tails`, append it. The length of the course is `len(tails)`. Otherwise, replace `tails[idx]` with `obstacle`. The length of the course is `idx + 1`. import bisect def longestObstacleCourseAtEachPosition(obstacles: list[int]) -> list[int]: tails = [] ans = [] for obs in obstacles: idx = bisect.bisect_right(tails, obs) if idx == len(tails): tails.append(obs) else: tails[idx] = obs ans.append(idx + 1) return ans 4. Maximize Score After N Operations Problem: Given $2n$ numbers, perform $n$ operations. In each operation $i$, choose two numbers $x, y$, remove them, and add $i \times \text{gcd}(x, y)$ to score. Maximize total score. Approach: Bitmask DP. State: `dp[mask]` - maximum score for numbers represented by `mask`. State Transition: Iterate $mask$ from $0$ to $2^{2n}-1$. If `mask` has an even number of set bits (meaning we can form pairs), find two unset bits $i, j$. `dp[mask | (1 The `op_num` is `(count_set_bits(mask) / 2) + 1`. import math def maxScore(nums: list[int]) -> int: n_pairs = len(nums) // 2 # Precompute GCDs gcd_matrix = {} for i in range(len(nums)): for j in range(i + 1, len(nums)): gcd_matrix[(i, j)] = math.gcd(nums[i], nums[j]) # dp[mask] = max score for numbers represented by mask dp = [0] * (1 > i) & 1: # if i-th bit is set for j in range(i + 1, len(nums)): if (mask >> j) & 1: # if j-th bit is set prev_mask = mask ^ (1 5. Concatenated Words Problem: Given a list of words, return all words that are formed by concatenating other words in the list. Approach: Trie + DP or DP with memoization. Sort words by length. DP with Memoization: For each word, check if it can be formed by concatenating smaller words already processed. `dp[i]` = true if `word[0...i-1]` is a concatenated word. For a word `s`, iterate $i$ from $0$ to `len(s)`. If `s[0...i-1]` is a valid word and `s[i...len(s)-1]` is a valid concatenated word, then `s` is a concatenated word. Store all words in a `set` for $O(1)$ lookup. class Solution: def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]: word_set = set(words) ans = [] def can_break(word: str, current_word_set: set[str]) -> bool: if not word: return False # An empty string cannot be a concatenated word itself dp = [False] * (len(word) + 1) dp[0] = True # Empty prefix is always "breakable" for i in range(1, len(word) + 1): for j in range(i): if dp[j] and word[j:i] in current_word_set: dp[i] = True break return dp[len(word)] words.sort(key=len) # Process shorter words first for i in range(len(words)): # Temporarily remove the current word from the set to prevent self-matching current_word = words[i] word_set.remove(current_word) if can_break(current_word, word_set): ans.append(current_word) word_set.add(current_word) # Add it back for subsequent checks return ans 6. Stone Game III Problem: Alice and Bob take turns taking 1, 2, or 3 stones from the beginning of a row. Maximize Alice's score minus Bob's score. Approach: Minimax DP. `dp[i]` represents the maximum score difference Alice can achieve starting from `piles[i:]`. State Transition: `dp[i] = max(sum(piles[i:i+k]) - dp[i+k])` for $k \in \{1, 2, 3\}$. `sum(piles[i:i+k])` is the score Alice gets. `-dp[i+k]` is the score Bob gets from remaining piles (from Alice's perspective, this is a loss). Base cases: If $i \ge n$, $dp[i] = 0$. def stoneGameIII(stoneValue: list[int]) -> str: n = len(stoneValue) dp = [0] * (n + 1) # dp[i] is max score diff starting from index i for i in range(n - 1, -1, -1): # Take 1 stone res = stoneValue[i] - dp[i + 1] if i + 1 0: return "Alice" elif dp[0] 7. Split Array With Same Average Problem: Check if array `A` can be split into two non-empty subarrays with the same average. Approach: DP with subset sums. The problem is equivalent to finding a subarray `B` of length `k` with sum `target_sum = (total_sum * k) / N`. State: `dp[k][s]` = true if it's possible to form a sum `s` using `k` elements. Optimization: `dp[s]` = set of possible lengths `k` to achieve sum `s`. Or, `dp[k]` = set of possible sums `s` using `k` elements. Algorithm: Calculate `total_sum` and `N`. Iterate `k` from $1$ to $N/2$. If `(total_sum * k) % N == 0`, calculate `target_sum = (total_sum * k) // N`. Check if a subset of `A` of size `k` sums to `target_sum`. This can be done with a bitmask DP or a `sum_possible[count][current_sum]` boolean array. To avoid duplicate elements in subset sum: iterate elements one by one. def splitArraySameAverage(nums: list[int]) -> bool: n = len(nums) total_sum = sum(nums) # Shift numbers to avoid negative sums if needed (not strictly necessary here as all nums >= 0) # This problem often involves sums, so it's good practice for general cases # For this problem, numbers are 0 to 10000, so sum can be large. # It's better to work with the original numbers. # dp[s] stores a set of possible lengths `k` that can sum up to `s`. # Sums can be up to N * 10000, so we use a map or shift. # A more efficient DP: dp[k] stores all possible sums using k elements. # dp[k] = set of sums achievable with k elements dp = [set() for _ in range(n // 2 + 1)] dp[0].add(0) # 0 elements can sum to 0 for num in nums: # Iterate k from high to low to avoid using the same number multiple times for k in range(n // 2, 0, -1): for current_sum in dp[k-1]: dp[k].add(current_sum + num) for k in range(1, n // 2 + 1): if (total_sum * k) % n == 0: target_sum = (total_sum * k) // n if target_sum in dp[k]: return True return False 8. Freedom Trail Problem: Given a `ring` and a `key`, find the minimum steps to spell `key`. Steps involve rotating `ring` and pressing a character. Approach: DP. `dp[k_idx][r_idx]` = min steps to spell `key[k_idx:]` with `ring[r_idx]` aligned at 12 o'clock. State Transition: To spell `key[k_idx]`, find all occurrences of `key[k_idx]` in `ring`. For each `ring_char_pos` of `key[k_idx]`: Calculate rotation steps from `r_idx` to `ring_char_pos`. `dp[k_idx][r_idx] = min(rotation_steps + 1 + dp[k_idx+1][ring_char_pos])`. (1 for pressing the button) from collections import defaultdict def findRotateSteps(ring: str, key: str) -> int: n, m = len(ring), len(key) # Store indices of each character in the ring char_indices = defaultdict(list) for i, char in enumerate(ring): char_indices[char].append(i) # dp[k_idx][r_idx] = min steps to spell key[k_idx:] # with ring[r_idx] at 12 o'clock dp = [[float('inf')] * n for _ in range(m + 1)] # Base case: no more characters in key, 0 steps for j in range(n): dp[m][j] = 0 # Iterate key characters from last to first for k_idx in range(m - 1, -1, -1): target_char = key[k_idx] # Iterate over all possible current ring positions for current_r_idx in range(n): # For each occurrence of target_char in ring for next_r_idx in char_indices[target_char]: # Calculate rotation steps dist = abs(current_r_idx - next_r_idx) rotation_steps = min(dist, n - dist) # Update dp dp[k_idx][current_r_idx] = min(dp[k_idx][current_r_idx], rotation_steps + 1 + dp[k_idx + 1][next_r_idx]) # Start with ring[0] at 12 o'clock return dp[0][0] 9. Minimum Falling Path Sum II Problem: Given an $n \times n$ grid, find the minimum falling path sum where no two adjacent elements in the path are in the same column. Approach: DP. `dp[i][j]` = min falling path sum ending at `grid[i][j]`. State Transition: `dp[i][j] = grid[i][j] + min(dp[i-1][k])` for all $k \ne j$. To efficiently find `min(dp[i-1][k])` for $k \ne j$: find the two smallest values in `dp[i-1]`. If `dp[i-1][j]` is the smallest, use the second smallest; otherwise, use the smallest. def minFallingPathSum(grid: list[list[int]]) -> int: n = len(grid) # dp[i][j] will store the minimum sum ending at grid[i][j] # We can optimize space by only storing the previous row's DP values prev_dp = grid[0] for i in range(1, n): current_dp = [0] * n # Find the two smallest values and their indices from prev_dp # This helps in quickly finding min(dp[i-1][k]) for k != j # Store (value, index) pairs sorted_prev = sorted([(val, idx) for idx, val in enumerate(prev_dp)]) min1_val, min1_idx = sorted_prev[0] min2_val, min2_idx = sorted_prev[1] if n > 1 else (float('inf'), -1) for j in range(n): if j == min1_idx: current_dp[j] = grid[i][j] + min2_val else: current_dp[j] = grid[i][j] + min1_val prev_dp = current_dp return min(prev_dp) 10. Cherry Pickup II Problem: Two robots start at `(0,0)` and `(0,cols-1)` in a grid. They move down, down-left, or down-right. Maximize cherries collected. Approach: 3D DP. `dp[r][c1][c2]` = max cherries robots can collect starting from `(r, c1)` and `(r, c2)` down to the bottom. State Transition: For each `(r, c1, c2)`: Iterate `nc1` from $c1-1$ to $c1+1$. Iterate `nc2` from $c2-1$ to $c2+1$. `dp[r][c1][c2] = grid[r][c1] + (grid[r][c2] if c1 != c2 else 0) + max(dp[r+1][nc1][nc2])`. Base cases: If $r = \text{rows}$, return 0. Handle boundary conditions for `nc1`, `nc2`. def cherryPickup(grid: list[list[int]]) -> int: rows, cols = len(grid), len(grid[0]) # dp[r][c1][c2] = max cherries from (r, c1) and (r, c2) down to bottom # Initialize with -1 to denote uncomputed states memo = {} def solve(r, c1, c2): if (r, c1, c2) in memo: return memo[(r, c1, c2)] # Base case: out of bounds if not (0 11. K Inverse Pairs Array Problem: Find the number of permutations of $1 \ldots n$ that have exactly $k$ inverse pairs. Approach: DP. `dp[i][j]` = number of permutations of $1 \ldots i$ with exactly $j$ inverse pairs. State Transition: When adding `i` to a permutation of $1 \ldots i-1$: If `i` is placed at the end, it creates 0 new inversions. If `i` is placed at the second to last, it creates 1 new inversion. ... If `i` is placed at the beginning, it creates $i-1$ new inversions. `dp[i][j] = sum(dp[i-1][j-x])` for $x \in [0, \min(j, i-1)]$. This sum can be optimized using prefix sums: `dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i]`. def kInversePairs(n: int, k: int) -> int: MOD = 10**9 + 7 # dp[i][j] = number of permutations of 1...i with j inverse pairs dp = [[0] * (k + 1) for _ in range(n + 1)] # Base case: for 1 element, 0 inverse pairs dp[1][0] = 1 for i in range(2, n + 1): # Calculate prefix sums for dp[i-1] to optimize the inner loop prefix_sum = [0] * (k + 1) prefix_sum[0] = dp[i-1][0] for j in range(1, k + 1): prefix_sum[j] = (prefix_sum[j-1] + dp[i-1][j]) % MOD for j in range(k + 1): # The sum is dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j - min(j, i-1)] # This is equivalent to prefix_sum[j] - prefix_sum[j - i] if j - i >= 0 # dp[i][j] = sum(dp[i-1][x]) for x in [j - (i-1), j] # This is prefix_sum[j] - prefix_sum[j - i] (if j - i >= 0) # Sum up dp[i-1][x] for x from max(0, j - (i-1)) to j # Using the optimized transition: # dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] # The term dp[i][j-1] accounts for placing `i` at any position but the first, # which adds 0, 1, ..., j-1 inversions. # dp[i-1][j] adds `i` at the end (0 new inversions). # We subtract dp[i-1][j-i] to remove cases where `i` adds i or more inversions # (which is not possible as `i` can add at most i-1 inversions). if j == 0: dp[i][j] = 1 # Only one way to have 0 inverse pairs (sorted array) else: val = (dp[i][j-1] + dp[i-1][j]) % MOD if j >= i: val = (val - dp[i-1][j-i] + MOD) % MOD # Add MOD before % for negative results dp[i][j] = val return dp[n][k] 12. Arithmetic Slices II - Subsequence Problem: Find the number of arithmetic subsequences with at least 3 elements. Approach: DP. `dp[i]` = a hashmap where `dp[i][diff]` stores the count of arithmetic subsequences ending at index `i` with common difference `diff` and length at least 2. State Transition: For each `nums[i]`: For each `nums[j]` where $j Calculate `diff = nums[i] - nums[j]`. `dp[i][diff]` is incremented by `dp[j][diff]` (subsequences of length $\ge 2$ ending at `j` extended by `nums[i]`) + 1 (new subsequence of length 2: `nums[j], nums[i]`). `ans` is incremented by `dp[j][diff]` (these are subsequences of length $\ge 3$). from collections import defaultdict def numberOfArithmeticSlices(nums: list[int]) -> int: n = len(nums) if n = 2 ending at j with this diff count_j_diff = dp[j][diff] # Extend subsequences of length >= 2 ending at j with nums[i] # This adds count_j_diff new subsequences of length >= 3 total_count += count_j_diff # Add current pair (nums[j], nums[i]) as a new subsequence of length 2 # And add all extended subsequences from dp[j][diff] dp[i][diff] += count_j_diff + 1 return total_count 13. Minimum Difficulty of a Job Schedule Problem: Schedule jobs over `d` days. Each day, complete at least one job. The difficulty of a day is the max difficulty of jobs done that day. Minimize total difficulty. Approach: DP. `dp[i][j]` = min difficulty to schedule first `j` jobs in `i` days. State Transition: `dp[i][j] = min(dp[i-1][k] + max_diff(jobs[k+1...j]))` for $k$ from $i-2$ to $j-1$. `max_diff(jobs[k+1...j])` is the maximum difficulty for jobs done on day `i`. Base cases: `dp[1][j]` = max difficulty of `jobs[0...j-1]`. def minDifficulty(jobDifficulty: list[int], d: int) -> int: n = len(jobDifficulty) if n 0 difficulty dp[0][0] = 0 # For day 1 (i=1): # dp[1][j] is the max difficulty of jobs[0...j-1] max_d = 0 for j in range(1, n + 1): max_d = max(max_d, jobDifficulty[j-1]) dp[1][j] = max_d for i in range(2, d + 1): # Number of days for j in range(i, n + 1): # Number of jobs (must be at least i) # To schedule j jobs in i days, the last day (day i) must handle jobs from k to j-1 # The previous i-1 days must handle k jobs # k must be at least i-1 (to accommodate i-1 days) and less than j current_day_max_diff = 0 for k_prev_jobs in range(j - 1, i - 2, -1): # k_prev_jobs from j-1 down to i-1 # jobs[k_prev_jobs] ... jobs[j-1] are done on day i current_day_max_diff = max(current_day_max_diff, jobDifficulty[k_prev_jobs]) if dp[i-1][k_prev_jobs] != float('inf'): dp[i][j] = min(dp[i][j], dp[i-1][k_prev_jobs] + current_day_max_diff) return dp[d][n] if dp[d][n] != float('inf') else -1 14. String Compression II Problem: Compress a string by removing at most `k` characters. Minimize length of compressed string. Approach: 3D DP. `dp[i][k][last_char_count]` = min length of compressed string for `s[i:]` with `k` removals, and `s[i-1]` was `last_char` with `last_char_count`. State: `dp[i][k][last_char_idx][last_char_freq]` represents the minimum compressed length for `s[i:]` given `k` removals, and the previous character considered was `last_char_idx` with `last_char_freq`. Length function: `len(count)` for $count \in \{1, 9, 99, \ldots\}$. $1 \to 1$, $2 \ldots 9 \to 2$, $10 \ldots 99 \to 3$, etc. Transition: For `s[i]`: Option 1: Delete `s[i]`. `dp[i+1][k-1][last_char_idx][last_char_freq]`. Option 2: Keep `s[i]`. If `s[i] == last_char`: increment `last_char_freq`. Update compressed length accordingly. If `s[i] != last_char`: start new group. `last_char_freq = 1`. def getLength(count): if count == 0: return 0 if count == 1: return 1 if 2 = 100 def getLengthOfOptimalCompression(s: str, k: int) -> int: n = len(s) # dp[i][k][last_char_idx][last_char_freq] # i: current index in s # k: remaining deletions # last_char_idx: index of the previous character (0-25 for 'a'-'z') # last_char_freq: frequency of the previous character # Using 101 for max_freq as max length can be 100 # Memoization dictionary memo = {} def solve(idx, remaining_k, last_char_code, last_char_freq): if (idx, remaining_k, last_char_code, last_char_freq) in memo: return memo[(idx, remaining_k, last_char_code, last_char_freq)] if idx == n: return 0 # All characters processed res = float('inf') # Option 1: Delete current character s[idx] if remaining_k > 0: res = min(res, solve(idx + 1, remaining_k - 1, last_char_code, last_char_freq)) # Option 2: Keep current character s[idx] current_char_code = ord(s[idx]) - ord('a') if current_char_code == last_char_code: # Same character, increment frequency # If freq was 1, now 2. Compressed length changes from 1 to 2. # If freq was 9, now 10. Compressed length changes from 2 to 3. # Current length contribution before s[idx] was getLength(last_char_freq) # New contribution after s[idx] is getLength(last_char_freq + 1) # So, change in length is getLength(last_char_freq + 1) - getLength(last_char_freq) new_len_contribution = getLength(last_char_freq + 1) - getLength(last_char_freq) res = min(res, new_len_contribution + solve(idx + 1, remaining_k, last_char_code, last_char_freq + 1)) else: # Different character, start a new group. New freq is 1. # Adds 1 to compressed length (for the char itself), plus 1 if count > 1 res = min(res, 1 + solve(idx + 1, remaining_k, current_char_code, 1)) memo[(idx, remaining_k, last_char_code, last_char_freq)] = res return res # Initial call: start at index 0, k deletions, no previous char (-1), freq 0 return solve(0, k, -1, 0) 15. Number of Ways to Stay in the Same Place After Some Steps Problem: A pointer is at index 0 in an array of length `arrLen`. In `steps` steps, move left, right, or stay. Find number of ways to end at index 0. Approach: DP. `dp[i][j]` = number of ways to reach position `j` in `i` steps. State Transition: `dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]) % MOD`. Handle boundary conditions for `j-1` and `j+1`. The maximum reachable position is `min(steps, arrLen - 1)`. Limit `j` iteration. def numWays(steps: int, arrLen: int) -> int: MOD = 10**9 + 7 # Max position the pointer can reach is min(steps, arrLen - 1) # Because if arrLen is very large, pointer can't go beyond 'steps' steps from 0. # And if steps is very large, pointer can't go beyond arrLen-1. max_pos = min(steps, arrLen - 1) # dp[i][j] = number of ways to be at position j after i steps # We can optimize space by only keeping track of the current and previous row # current_dp[j] = number of ways to be at position j after `s` steps # prev_dp[j] = number of ways to be at position j after `s-1` steps prev_dp = [0] * (max_pos + 1) prev_dp[0] = 1 # After 0 steps, 1 way to be at position 0 for s in range(1, steps + 1): current_dp = [0] * (max_pos + 1) for j in range(max_pos + 1): # Stay at j current_dp[j] = prev_dp[j] # Come from j-1 if j > 0: current_dp[j] = (current_dp[j] + prev_dp[j-1]) % MOD # Come from j+1 if j 16. Painting the Walls Problem: Given `cost` and `time` for `n` walls. A paid painter takes `cost[i]` and `time[i]`. A free painter takes 1 unit of time to paint one wall. Minimize total cost to paint all `n` walls. Approach: DP. This is a variation of Knapsack. `dp[t]` = minimum cost to paint `t` walls where `t` is the "net time" obtained from paid painters. State: `dp[j]` = minimum cost to paint `j` walls using paid painters, where `j` is the number of walls painted by paid painters. Refined State: `dp[time_budget]` = minimum cost to get `time_budget` units of "free time" from paid painters. If a paid painter paints wall `i` with `cost[i]` and `time[i]`, they paint 1 wall and give `time[i]` units of free time. Effectively, `time[i]+1` walls are painted for `cost[i]`. Let `dp[j]` be the minimum cost to paint `j` walls (by paid painters) such that the total "free time" obtained is at least `j`. Correct DP State: `dp[j]` = minimum cost to paint `j` walls (by paid painters) such that we accumulate enough "free time" to paint `j` additional walls. This is equivalent to finding the min cost to get `j` units of time from paid painters. Let `dp[time_sum]` be the minimum cost to achieve `time_sum` units of "free time". Alternative Knapsack: Let `dp[i]` be the minimum cost to paint `i` walls. For each wall `k` (with `cost[k]` and `time[k]`): Iterate `j` from `n` down to `0`. `dp[j] = min(dp[j], dp[max(0, j - time[k] - 1)] + cost[k])`. def paintWalls(cost: list[int], time: list[int]) -> int: n = len(cost) # dp[i] = minimum cost to paint 'i' walls (total walls, including free ones) # The maximum 'time' for a single painter is N-1. # The total 'time' could be up to N * N (if all painters take N-1 time). # But we only need to paint N walls. # The total "free time" we need is at most N. # If a paid painter paints a wall, they take `cost[i]` and `time[i]`. # This means 1 wall is painted by a paid painter. # And `time[i]` walls can be painted by a free painter "for free". # So, effectively, `time[i] + 1` walls are painted for `cost[i]`. # Let dp[j] be the minimum cost to paint 'j' walls by the paid painter, # such that the number of walls painted by the free painter # (due to the time accumulated) is at least (N - j). # Or, simpler: dp[j] = min cost to paint 'j' walls by paid painters # and accumulate 'j' units of 'free time'. # A better formulation: dp[i] is the minimum cost to paint 'i' walls, # where 'i' represents the *net* walls painted by paid painters (i.e. 'i' walls are painted by paid painters, # and the remaining N-i walls are painted by free painters using the accumulated time.) # Let dp[t] be the minimum cost to get 't' units of free time. # The maximum free time we might need is N. # The sum of all time[i] can be large, but we only care about free time up to N. # Max possible time sum is N * (N-1) ~ 500 * 500 = 250,000. # We need to paint N walls. If we pay for `i` walls, we need `N-i` free walls. # `dp[j]` = minimum cost to paint `j` walls using paid painters, # such that the total time accumulated from these painters is at least `j`. # Let dp[j] be the minimum cost to paint `j` walls. # The state `j` here represents the number of walls painted by *paid* painters. # The free walls are covered by the time accumulated. # The total "time capacity" needed is N. # We can transform this into a 0/1 knapsack problem. # For each wall `i`, we have item `(cost[i], time[i])`. # If we pick wall `i` with cost `c` and time `t`: # We pay `c`. This wall is painted. # We get `t` units of "free time". This `t` free time can paint `t` other walls. # So, effectively, we paint `1 + t` walls for `c` cost. # We need to paint `N` walls. # Let `dp[j]` be the minimum cost to paint `j` walls. # dp[i] = min cost to get 'i' units of "net free walls" # where "net free walls" = (walls painted by paid painters + time from paid painters) # We need to reach `N` net walls. # The key is that `time[j]` free walls can be painted. # If we paint wall `j` for `cost[j]`, we get `time[j]` free walls. # Total walls painted = `1` (paid) + `time[j]` (free). # So, we are looking for `dp[walls_to_paint_by_paid]` such that # the total `time_from_paid_painters` >= `N - walls_to_paint_by_paid`. # This means `time_from_paid_painters + walls_to_paint_by_paid >= N`. # Let dp[t] be the minimum cost to paint 't' walls *by paid painters* # such that the *sum of times* for these paid painters is at least (N - t). # This means we need to find `dp[t]` such that `t + sum_of_times >= N`. # Max possible `time` sum is `sum(time)`. # Max possible `time` for a single wall is $N-1$. # Max effective capacity for `dp` state is `2 * N`. # `dp[j]` = min cost to achieve `j` "effective walls" (paid + free) # where `j` ranges from 0 to N. # Let `dp[j]` be the minimum cost to paint `j` walls (by paid painters) # such that the total sum of `time` for these `j` paid walls is at least `N - j`. # We want to minimize cost. # The state `j` represents the *net* number of walls painted (paid walls + free walls). # `dp[j]` = min cost to paint `j` walls. # `dp[i]` = minimum cost to paint `i` walls (where `i` refers to the total number of walls painted by *paid* painters) # such that the sum of `time` for these `i` paid painters is at least `N - i`. # `dp[j]` stores the minimum cost to paint `j` walls (by paid painters). # The `j` here is the count of walls painted by paid painters. # We want to find `min(dp[j])` where the total `time` from these `j` painters is at least `N-j`. # Let dp[i] be the minimum cost needed to paint 'i' walls (total walls, paid + free). # Max walls to paint is N. # dp array size `N+1`. Initialize `dp[0]=0`, others `inf`. # Iterate through painters. For each painter `(cost_i, time_i)`: # Iterate `j` from `N` down to `1`. # `dp[j] = min(dp[j], dp[max(0, j - (time_i + 1))] + cost_i)` # Or, the standard knapsack approach: # dp[j] = min cost to achieve 'j' units of 'time_sum' from paid painters. # Max time sum can be N * (N-1) ~ 250000. # The target `j` should be at least `N`. # `dp[t]` = minimum cost to have a total `time` of at least `t`. # `dp` array size `N + max(time) + 1` or `N + N * (N-1) + 1`? # Max value for `time` can be $N-1$. So total time is $N * (N-1)$. # But we only need to "cover" `N` walls. # The `time` from a paid painter allows `time[i]` walls to be painted for free. # So if we pick `k` paid painters, we accumulate `sum(time_k)` free walls. # We also paint `k` walls by paid painters. # Total walls painted = `k + sum(time_k)`. We need this to be $N$. # Minimize `sum(cost_k)`. # This is a 0/1 knapsack problem variant. # `dp[j]` = minimum cost to paint `j` walls (where `j` is the effective number of walls painted by free painters) # `j` can go up to N. # `dp[i]` = min cost to get `i` units of "free time" (from paid painters). # The capacity is `N`. # Let dp[j] be the minimum cost to paint `j` walls (by paid painters) # such that the total free time generated is at least `N - j`. # Let `dp[t_sum]` be the minimum cost to generate `t_sum` units of time. # We need to find `min(dp[t_sum] + cost_of_t_sum_painters)` such that `t_sum + num_paid_painters >= N`. # A simpler DP state: # `dp[j]` = min cost to paint `j` walls (by paid painters) # such that the sum of time for these `j` painters is sufficient to paint the remaining `N-j` walls. # `dp[i]` represents min cost to paint `i` walls (where `i` is the count of walls painted by paid painters) # such that the total `time` accumulated from these `i` painters is at least `N-i`. # Let `dp[i]` be the minimum cost to paint exactly `i` walls (total walls). # `dp` array of size `N+1`. `dp[0] = 0`, others `inf`. # For each `(c, t)` pair: # Iterate `j` from `N` down to `0`: # `dp[j] = min(dp[j], dp[max(0, j - (t+1))] + c)` # This logic seems correct. `j - (t+1)` means we need to paint `j - (t+1)` walls before this one. dp = [float('inf')] * (n + 1) dp[0] = 0 # 0 cost to paint 0 walls for c, t in zip(cost, time): # Iterate from N down to 1 for j in range(n, 0, -1): # If we choose this painter (c, t): # The current painter paints 1 wall (paid) and 't' walls for free. Total t+1 walls. # So, we need to have painted j - (t+1) walls before this. prev_walls_needed = max(0, j - (t + 1)) if dp[prev_walls_needed] != float('inf'): dp[j] = min(dp[j], dp[prev_walls_needed] + c) return dp[n] 17. Minimum Cost to Cut a Stick Problem: Given a stick of length `n` and an array of `cuts`. Minimize total cost to make all cuts. Cost of a cut is the length of the stick being cut. Approach: Interval DP. Sort `cuts` and add $0$ and $n$ to `cuts`. `dp[i][j]` = min cost to cut the stick segment `cuts[i]` to `cuts[j]`. State Transition: For each segment `(cuts[i], cuts[j])`: Iterate `k` from $i+1$ to $j-1$ (potential first cut in this segment). `dp[i][j] = min(dp[i][j], (cuts[j] - cuts[i]) + dp[i][k] + dp[k][j])`. Base cases: `dp[i][i+1] = 0` (segment of length 1, no cuts needed). def minCost(n: int, cuts: list[int]) -> int: # Add 0 and n to cuts and sort them cuts = sorted([0] + cuts + [n]) num_cuts = len(cuts) # dp[i][j] = min cost to cut the stick segment from cuts[i] to cuts[j] # The length of this segment is cuts[j] - cuts[i] dp = [[0] * num_cuts for _ in range(num_cuts)] # `length` refers to the number of cut points in the subproblem (j - i + 1) # or the actual length of the segment (cuts[j] - cuts[i]) # Iterate over possible lengths of the sub-stick (represented by index difference) for length in range(2, num_cuts): # length = number of cut points - 1 for i in range(num_cuts - length): j = i + length # The cost of cutting this segment current_segment_length = cuts[j] - cuts[i] min_cost_for_segment = float('inf') # Try every possible first cut 'k' within this segment for k in range(i + 1, j): # cost = current_segment_length + cost_left_subproblem + cost_right_subproblem min_cost_for_segment = min(min_cost_for_segment, current_segment_length + dp[i][k] + dp[k][j]) dp[i][j] = min_cost_for_segment return dp[0][num_cuts - 1] 18. Profitable Schemes Problem: Given `n` members, `minProfit`, and lists `group`, `profit`. Find number of profitable schemes. Approach: 2D DP (or 3D if optimized). `dp[i][j]` = number of schemes with `i` members and at least `j` profit. State Transition: `dp[num_members_used][current_profit]` = count. For each crime `k` (`group[k]`, `profit[k]`): Iterate `i` from `n` down to `group[k]`. Iterate `j` from `minProfit` down to `0`. `dp[i][j] = (dp[i][j] + dp[i - group[k]][max(0, j - profit[k])]) % MOD`. def profitableSchemes(n: int, minProfit: int, group: list[int], profit: list[int]) -> int: MOD = 10**9 + 7 # dp[j][k] = number of schemes using 'j' members to achieve 'k' profit # The 'k' profit here is capped at minProfit, meaning any profit >= minProfit is counted as minProfit. # dp[j] = array where dp[j][p] is the number of ways to get exactly 'p' profit # using 'j' members. # This approach is usually: dp[member_count][profit_amount] # dp[j][p] means number of ways to achieve profit 'p' using 'j' members. # Initialize dp[members][profit] # dp[p] = number of ways to get *exactly* 'p' profit using *current* number of members # Or, dp[members_used][profit_achieved] # dp[j][p] = number of ways to achieve profit 'p' using exactly 'j' members. # The profit 'p' needs to be capped at minProfit. # If profit `p` exceeds `minProfit`, we store it in `dp[j][minProfit]`. # Let dp[j] be an array where dp[j][p] is the number of ways to achieve profit `p` using `j` members. # We can optimize space by only keeping track of the current number of members. # dp[p] = number of ways to achieve exactly profit 'p' with current members # `dp[j]` = number of schemes with `j` members and `minProfit` profit. # dp[p] = number of ways to achieve *exactly* profit `p` # Initialize dp with `dp[0] = 1` for 0 profit, 0 members. # Iterate through (g, p) for each crime: # For members `i` from `n` down to `g`: # For profit `j` from `minProfit` down to `0`: # `dp[i][min(minProfit, j + p_crime)] += dp[i-g][j]` # dp[j][k] = number of ways to achieve at least profit `k` using exactly `j` members. # Initialize dp[0][0] = 1 (0 members, 0 profit, 1 way - do nothing) dp = [[0] * (minProfit + 1) for _ in range(n + 1)] dp[0][0] = 1 # 1 way to get 0 profit with 0 members. for g, p in zip(group, profit): # Iterate members from high to low to avoid using the same crime multiple times for i in range(n, g - 1, -1): # Iterate profit from high to low for j in range(minProfit, -1, -1): # Calculate new profit after doing this crime new_profit = min(minProfit, j + p) # Add ways from previous state (i-g members, j profit) dp[i][new_profit] = (dp[i][new_profit] + dp[i - g][j]) % MOD # Sum up all ways to achieve at least minProfit with any number of members 19. Number of Ways to Form a Target String Given a Dictionary Problem: Given a list of words `words` and a `target` string. Form `target` by picking characters from columns of `words`. Approach: DP. `dp[i][j]` = number of ways to form `target[i:]` using characters from `words` starting at column `j`. Precomputation: Create `freq[col_idx][char_idx]` = frequency of `char_idx` at `col_idx` across all `words`. State Transition: `dp[i][j]` (to form `target[i:]` using columns `j` onwards): Option 1: Skip column `j`. `dp[i][j+1]`. Option 2: Use `target[i]` from column `j`. `count = freq[j][target[i]]`. `dp[i][j] = (dp[i][j] + count * dp[i+1][j+1]) % MOD`. from collections import defaultdict def numWays(words: list[str], target: str) -> int: MOD = 10**9 + 7 len_target = len(target) len_word = len(words[0]) # All words have same length # Precompute character frequencies for each column # char_counts[col_idx][char_code] = count char_counts = [defaultdict(int) for _ in range(len_word)] for word in words: for col_idx, char in enumerate(word): char_counts[col_idx][char] += 1 # dp[i][j] = number of ways to form target[i:] using columns j onwards # dp[target_idx][word_col_idx] # We can optimize space by only using 2D DP for `i` and `j` # or even 1D DP for `target_idx` if we iterate `word_col_idx` carefully. # dp[i][j] represents number of ways to form target[i:] considering words from column j onwards # Base cases: # dp[len_target][j] = 1 for all j (empty target string, 1 way to form it) # dp[i][len_word] = 0 for i 20. Number of Music Playlists Problem: Create a playlist of `goal` songs from `n` unique songs. Each song must be played at least once. A song can only be played again after `k` other songs have been played. Approach: DP. `dp[i][j]` = number of playlists of length `i` with `j` unique songs. State Transition: To form a playlist of length `i` with `j` unique songs: Option 1: Add a new song. Previous state: `dp[i-1][j-1]` (length `i-1`, `j-1` unique songs). Number of new songs available: `n - (j-1)`. Contribution: `dp[i-1][j-1] * (n - (j-1))`. Option 2: Add an old song. Previous state: `dp[i-1][j]` (length `i-1`, `j` unique songs). Number of old songs available: `j - k` (if `j > k`, must be played at least `k` songs ago). If `j Contribution: `dp[i-1][j] * max(0, j - k)`. def numMusicPlaylists(n: int, goal: int, k: int) -> int: MOD = 10**9 + 7 # dp[i][j] = number of playlists of length 'i' that contain exactly 'j' unique songs # goal: total length of playlist # n: total unique songs available # k: a song can only be played again after k other songs have been played # dp table dimensions: (goal + 1) x (n + 1) dp = [[0] * (n + 1) for _ in range(goal + 1)] # Base case: 0 length playlist, 0 unique songs, 1 way (empty playlist) dp[0][0] = 1 for i in range(1, goal + 1): # Current playlist length for j in range(1, n + 1): # Current number of unique songs # Case 1: Add a new song # We had j-1 unique songs in a playlist of length i-1. # Now we add a new song from the remaining (n - (j-1)) available songs. if j > 0: # Must have at least 1 unique song to add dp[i][j] = (dp[i][j] + dp[i-1][j-1] * (n - (j-1))) % MOD # Case 2: Add an existing song # We had j unique songs in a playlist of length i-1. # Now we add an existing song. # Condition: the song must have been played at least k songs ago. # This means there are (j - k) songs that are eligible to be replayed. # If j k: # Only if more than k unique songs have been played, can we replay. dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k)) % MOD return dp[goal][n]