DP Flashcards
Regular Expression Matching (Hard)
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Initialize dp[s.length + 1][p.length + 1] with false
dp[0][0] = true (empty string matches empty pattern)
dp[i][0] = false since non-empty string cannot match empty pattern
dp[0][j] = empty strings that match patterns must be of form XXX*, so pattern length needs to be even and character at even should be *
iterate pattern for j = 2, j += 2
if p[j - 1] = * dp[0][j] = d[0][j - 2]
double for i/j starting at 1/1
if s[i - 1] = p[j - 1] || p[j - 1] = .
dp[i][j] = dp[i - 1][j - 1]
else if p[j - 1] = * if p[j - 2] != . & p[j - 2] != s[i - 1] treat pattern as empty dp[i][j] = dp[i][j - 2] else handle empty & multiple case dp[i][j] = dp[i][j - 2] || dp[i - 1][j]
return dp[s.length][p.length]
Time - O(s.length * p.length)
Space - O(s.length * p.length)
Trapping Rain Water (Hard)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Initialize water to zero
create arrays to store left and right running maxes
leftMax[0] = height[0]
rightMax[height.length - 1] = height[height.length - 1]
iterate heights forwards and backwards
leftMax[i] = max(height[i], leftMax[i - 1])
rightMax[i] = max(height[i], rightMax[i + 1]
iterate and add water
water += min(leftMax[i], rightMax[i]) - height[i]
Time - O(n)
Space - O(n)
Climbing Stairs (Easy)
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
return 1 for n = 1 initialize dp - array(n + 1) dp[1] = 1; dp[2] = 2; iterate from i = 3, i <=n dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
Decode Ways (Medium)
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
dp = array(s.length + 1).fill(0) dp[0] = 1 dp[1] = s[0] === 0 ? 0 : 1
iterate i = 2 i < dp.length
if (s[i - 1] != 0)
dp[i] += dp[i - 1]
if (isValidTwoDigit)
dp[i] += dp[i - 2]
isValidTwoDigit:
num = Number(s.slice(i - 2, i)
num >= 10 & num <= 26
Time - O(n)
Space - O(n)
Best Time to Buy and Sell Stock I (Easy)
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
min = Inf max = -Inf
calc running min
and max difference w/ min
min = min(prices[i], min) max = max(proces[i] - min, max)
return max
Time - O(n)
Space - O(1)
Best Time to Buy and Sell Stock II (Easy)
Say you have an array prices for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
max = 0
iterate i=1 i < prices.length
if (prices[i] > prices[i - 1])
max += prices[i] - prices[i - 1]
return max
Time - O(n)
Space - O(1)
Best Time to Buy and Sell Stock III (Hard)
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
dp = 3 x prices.length array fill 0
for (t = 1 t<= 2)
maxThusFar = -Inf
for (d = 1 d< prices.length)
maxThusFar = max(maxThusFar, dp[t - 1][d - 1] - prices[d - 1])
dp[t][d] = max(dp[t][d - 1], maxThusFar + prices[d])
return dp[2][prices.length - 1]
Time - O(kn) where k = 2 so O(n)
Space - O(kn) => O(n)
Best Time to Buy and Sell Stock IV (Hard)
Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
if k > prices.length / 2, problem reduces to Buy and Sell Stock II b/c you can make as many transactions as you like
dp = array(prices.length).fill(0)
t = 1, t <= k, t++ min = prices[0] max = 0
i = 0, i < prices.length min = min(min, prices[i] - dp[i]) max = max(max, prices[i] - min) dp[i] = max
return dp.pop()
Time:
O(n) for k > n / 2
O(kn) otherwise
Space:
O(1) for K > n / 2
O(n) otherwise
Word Break I (Medium)
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
create dictionary set from wordDict
dp = array(s.length + 1).fill(false)
dp[0] = true i = 1 i <= s.length j = 0 j < i if (dp[j] && dict.has(s.slice(j, i)) dp[i] = true break
return dp[s.length]
Time - O(n^3)
Space - O(n)
Word Break II (Hard)
create stringChars, wordChars, words sets
add each char of string s to stringChars
add each word of wordDict to words and each char of word to wordChars
iterate through stringChars and verify each char of string is also in wordChars, otherwise return empty array
dp = array(s.length + 1).fill(new Set())
dp[0].add('')
i = 1, i <= s.length
sublist = []
j = 0 j < i
word = s.slice(j, i)
if words.has(word)
iterate through dp[j] set and push ${subsentence}${word}.trim() to sublist
add sublist to dp[i] set
return dp[s.length] set values
Range Sum Query (Easy)
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
initialize with this.sum = array(nums.length + 1).fill(0)
i = 1 i<= nums.length
sum[i] = sum[i - 1] + nums[i - 1]
sumRange(i, j):
return sum[j + 1] - sum[i]
Range Sum Query 2D (Medium)
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
initialize m + 1 x n + 1 array fill 0
r = 0 r < m
c = 0 c < n
sum[r + 1][c + 1] = sum[r + 1][c] + sum[r][c + 1] + matrix[r][c] - sum[r][c]
sumRegion(row1, col1, row2, col2):
return sum[r2 + 1][c2 + 1] - sum[r1][col2 + 1] - sum[r2 + 1][c1] + sum[r1][c1]
Time - O(1) per query, O(mn) precomputation
Space - O(mn)
Coin Change (Medium)
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
minCoins = array(amount + 1).fill(Infinity) minCoins[0] = 0
const coin of coins
j = 1 j<= amount
if coin <= j
minCoins[j] = min(minCoins[j], minCoins[j - coin] + 1
return minCoins[amount]
Time - O(coins.length * amount)
Space - O(amount)
Partition Equal Subset Sum (Medium)
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
calc total sum of nums
if sum is odd return false b/c can’t divide equally w/ ints
calc half sum
initialize dp nums.length + 1 x halfSum + 1, fill false
dp[0][0] = true (empty subset can sum to zero)
i = 1, i <=n num = nums[i - 1] j = 0, j <= subsetSum if (j < num) dp[i][j] = dp[i - 1][j] else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]
return dp[nums.length][subsetSum]
Time - O(n * sum)
Space - O(n * sum)
Maximum Sum of 3 Non-Overlapping Subarrays (Hard)
In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.
Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
m = 3 n = nums.length 2 m+1 x n+1 dp arrays fill 0 dp and index and a cumulative sum n + 1 array fill 0 sum[i] = sum[i - 1] + nums[i - 1]
i = 1 i <= m j = i * k, j <= n current = dp[i - 1][j - k] + sum[j] - sum[j - k] if current > dp[i][j - 1] dp[i][j] = current index[i][j] = j - k else dp[i][j] = dp[i][j - 1] index[i][j] = index[i][j - 1]
subarrayIndex = array(m) fill 0
subarrayIndex[m - 1] = index[m][n]
i = m - 2, i >= 0
subarrayIndex[i] = index[i + 1][subarrayIndex[i + 1]]
return subarrayIndex
Time - O(mn)
Space - O(mn)
