6 drills · 6 pattern exercises · 12 micro drills
Patterns used in this topic, with difficulty breakdown.
Count the number of ways to walk from the top-left to the bottom-right of a grid, only moving right or down.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Count the number of ways to walk from the top-left to the bottom-right of a grid, only moving right or down.
dp[i][j] = number of ways to reach cell (i,j). Each cell can only come from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. Optimize to a single row since we only look at the previous row.
Prompt
A robot is in the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?
Solution
def unique_paths(m, n):
row = [1] * n # base: top row all 1s
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1] # above + left
return row[-1]
# Test: unique_paths(3, 7) == 28
# Test: unique_paths(3, 2) == 3In plain English: Find the longest sequence of characters that appears in both strings (not necessarily contiguous).
dp[i][j] = LCS of text1[:i] and text2[:j]. If chars match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, take max of skipping either character: max(dp[i-1][j], dp[i][j-1]).
Prompt
Given two strings text1 and text2, return the length of their longest common subsequence.
Solution
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # chars match: extend the LCS by 1
else:
# skip one char from either string and keep the better result
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# Test: longest_common_subsequence("abcde", "ace") == 3 ("ace")
# Test: longest_common_subsequence("abc", "def") == 0In plain English: Find the fewest single-character edits (insert, delete, or replace) needed to turn one word into another.
dp[i][j] = edit distance of word1[:i] and word2[:j]. If chars match, no cost (take diagonal). Otherwise, 1 + min(insert, delete, replace) = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).
Prompt
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 into word2.
Solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# base cases: transforming to/from empty string
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
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] # no edit needed
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1], # replace
)
return dp[m][n]
# Test: min_distance("horse", "ros") == 3
# Test: min_distance("intention", "execution") == 5In plain English: Count how many different ways you can make change for a given amount using unlimited coins of each denomination.
Unbounded knapsack variant. dp[j] = number of ways to make amount j. Process coins in outer loop to avoid counting permutations (order doesn't matter). For each coin, dp[j] += dp[j - coin].
Prompt
Given an amount and a list of coin denominations, return the number of combinations that make up that amount. You may use each coin an unlimited number of times.
Solution
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make 0: use nothing
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[amount]
# Test: change(5, [1,2,5]) == 4 ({5}, {2+2+1}, {2+1+1+1}, {1*5})
# Test: change(3, [2]) == 0In plain English: Assign a plus or minus sign to each number so they all add up to a target. Count the ways.
Reduce to subset sum: if P is the positive subset sum, then P - (total - P) = target, so P = (total + target) / 2. Now count subsets that sum to P using 0/1 knapsack DP.
Prompt
Given an integer array nums and a target, assign + or - to each number to make the sum equal to target. Return the number of ways.
Solution
def find_target_sum_ways(nums, target):
total = sum(nums)
if (total + target) % 2 != 0 or abs(target) > total:
return 0
subset_sum = (total + target) // 2
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for j in range(subset_sum, num - 1, -1): # reverse for 0/1
dp[j] += dp[j - num]
return dp[subset_sum]
# Test: find_target_sum_ways([1,1,1,1,1], 3) == 5
# Test: find_target_sum_ways([1], 1) == 1In plain English: Check if a third string is a valid interleaving of two other strings, keeping the order of characters from each.
dp[i][j] = can s1[:i] and s2[:j] interleave to form s3[:i+j]? Transition: dp[i][j] is True if we can extend from dp[i-1][j] by matching s1[i-1], or from dp[i][j-1] by matching s2[j-1].
Prompt
Given strings s1, s2, and s3, determine whether s3 is formed by interleaving s1 and s2 (maintaining their relative order).
Solution
def is_interleave(s1, s2, s3):
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
# dp[i][j] = True if s3[:i+j] can be formed by interleaving s1[:i] and s2[:j]
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
# extend from s1 (row above) or s2 (col left) if the next char matches s3
dp[i][j] = (
(dp[i-1][j] and s1[i-1] == s3[i+j-1]) or
(dp[i][j-1] and s2[j-1] == s3[i+j-1])
)
return dp[m][n]
# Test: is_interleave("aabcc", "dbbca", "aadbbcbcac") == True
# Test: is_interleave("aabcc", "dbbca", "aadbbbaccc") == False6 exercises: spot the signals, pick the method, avoid the trap.
Given an m×n grid, count the number of unique paths from top-left to bottom-right (only move right or down).
Signals
1D DP row: dp[j] += dp[j-1]. O(m*n) time, O(n) space.
C(m+n-2, m-1) — direct combinatorial formula. O(m+n) time.
Trap
The combinatorial approach is O(1) space but watch for integer overflow in other languages.
Given two strings, find the length of their longest common subsequence.
Signals
dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1]). O(mn).
Same 2D table. Can optimize to 1D with careful row management. O(mn) time, O(n) space.
Trap
This is subsequence, not substring — characters don't need to be consecutive.
Given two words, find the minimum number of operations (insert, delete, replace) to convert one to the other.
Signals
dp[i][j] = dp[i-1][j-1] if match, else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). O(mn).
1D optimization with prev variable. O(mn) time, O(n) space.
Trap
Don't forget the base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).
Given coins and an amount, find the number of WAYS to make the amount (unlimited supply).
Signals
dp[a] += dp[a - coin] for each coin. Outer loop on coins avoids counting permutations. O(amount * coins).
Same. The key insight is coin-first loop gives combinations, not permutations.
Trap
If you iterate amounts in the outer loop, you count permutations (1+2 and 2+1 as different). Coins first = combinations.
Given nums and a target, assign + or - to each number to reach target. Count the number of ways.
Signals
Transform to subset sum: find subsets summing to (total+target)/2. Classic 0/1 knapsack. O(n * sum).
Recursive with memo on (index, current_sum). O(n * sum) but larger constant.
Trap
If (total + target) is odd or target > total, answer is 0. The math transformation is the key insight.
Given strings s1, s2, s3, determine if s3 is formed by interleaving s1 and s2.
Signals
dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1]). O(mn).
Recursive with memo on (i, j). Same O(mn) but stack overhead.
Trap
Check len(s1) + len(s2) == len(s3) first. If not, immediately return False.
12 quick recall drills to reinforce this topic.
Sortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))Transpose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.
n = len(m)
for i in range(n):
for j in range(i+1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
row.reverse()Backtracking on tree: append node, recurse, pop. Collect path copy at valid leaves. Classic tree + backtrack combo.
def pathSum(root, targetSum):
res = []
def dfs(node, remaining, path):
if not node: return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
res.append(path[:]) # copy!
dfs(node.left, remaining - node.val, path)
dfs(node.right, remaining - node.val, path)
path.pop() # backtrack
dfs(root, targetSum, [])
return res2D interval DP. Iterate i from bottom-up so dp[i+1] is already computed. Equivalent to LCS(s, reverse(s)).
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wCounting coin combinations iterates coins outer to avoid permutation double-counting.
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]Unbounded knapsack DP: iterate coins outer, amounts inner. Classic DP problem.
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)Track farthest reachable and current boundary. Increment jumps when boundary is hit.
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthestTransform target sum into a subset-sum problem via (total + target) / 2.
total = sum(nums)
if (total + target) % 2: return 0
s = (total + target) // 2
dp = [0] * (s + 1)
dp[0] = 1
for n in nums:
for j in range(s, n-1, -1):
dp[j] += dp[j - n]Reduces to 0/1 knapsack: can we pick a subset summing to total/2? Backwards loop prevents item reuse.
def canPartition(nums):
total = sum(nums)
if total % 2: return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for j in range(target, x - 1, -1): # backwards!
dp[j] = dp[j] or dp[j - x]
return dp[target]Prefix sum gives O(1) range queries after O(n) build. p[r+1] - p[l] = sum(a[l..r]). Off-by-one: p has length n+1.
p = [0] * (len(a) + 1)
for i in range(len(a)):
p[i+1] = p[i] + a[i]
# range sum [l, r] inclusive:
total = p[r+1] - p[l]