Dynamic Programming Flashcards
- Best Time to Buy and Sell Stock III
Solved
Hard
Topics
Companies
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 105 0 <= prices[i] <= 105
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
Calculate max profit at every step from the back. I.e imagine going from i to n for each i (keep track of max seen so far instead of min in the first approach)
Calculate max profit at every step from front and from back
# Then sum them up, return the max.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
trades = [0] * len(prices)
buy = 0
sell = 0
r = 1
while r < len(prices):
profit = prices[r] - prices[buy]
trades[r] = max(profit, trades[r-1])
if prices[r] < prices[buy]:
buy = r
r += 1
r = len(prices) - 2
sell = r+1
profit = 0
while r >= 0:
profit = max(profit, prices[sell] - prices[r])
trades[r] = trades[r] + profit
if prices[r] > prices[sell]:
sell = r
r-=1
return max(trades)
- Best Time to Buy and Sell Stock with Cooldown
Solved
Medium
Topics
Companies
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
Constraints:
1 <= prices.length <= 5000 0 <= prices[i] <= 1000
O(n), O(n) Expected.
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
Memoization: O(n), O(n)
~~~
from functools import cache
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def stock(i, buying):
if i >= len(prices):
return 0
# do nothing.
cooldown = stock(i+1, buying)
if buying:
# buy
action = stock(i+1, not buying) - prices[i]
else:
#sell
action = stock(i+2, not buying) + prices[i]
return max(action, cooldown)
return stock(0, True) ~~~
State machine O(n), O(n)
~~~
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# States:
# Held: Holding stock after buying, or just continue holding it from before.
# Sold: Sold the stock here after holding it.
# Cooldown: You either sold the stock before this, or you just keep on being in cooldown
# sold = held[i-1] + prices[i]
# held = max(held[i-1], cooldown[i-1] - prices[i])
# cooldown = max(cooldown[i-1], sold[i-1])
cooldown = 0
held = float(‘-inf’) # impossible to be in held at 0 since you haven’t bought yet.
sold = float(‘-inf’)
for i in range(len(prices)):
sold, cooldown, held = held + prices[i], max(cooldown, sold), max(held, cooldown - prices[i])
return max(sold, cooldown)
~~~
- Climbing Stairs
Solved
Easy
Topics
Companies Amazon, FB
Hint
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
https://leetcode.com/problems/climbing-stairs/description/
class Solution(object):
def climbStairs(self, n):
“””
:type n: int
:rtype: int
“””
if n < 3:
return n
step_1 = 1
step_2 = 2
for idx in range(2, n):
step_1, step_2 = step_2, (step_1 + step_2)
return step_2
- Min Cost Climbing Stairs
Solved
Easy
Topics
Companies
Hint
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Constraints:
2 <= cost.length <= 1000 0 <= cost[i] <= 999
https://leetcode.com/problems/min-cost-climbing-stairs/description/
Trick here is to set the cost of reaching step 0 and 1 to 0 as we can start there without paying any cost
# When we need to leave the position we need to pay the cost, so we calculate cost to reach n-1 and n-2 + their respective costs to leave that spot.
class Solution(object):
def minCostClimbingStairs(self, cost):
“””
:type cost: List[int]
:rtype: int
“””
steps = [0] * (len(cost) + 1)
for n in range(2, len(cost) + 1):
steps[n] = min(steps[n-1] + cost[n-1], steps[n-2] + cost[n-2])
return steps[-1]
- House Robber
Solved
Medium
Topics
Companies
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 100 0 <= nums[i] <= 400 https://leetcode.com/problems/house-robber/description/
Either pick previous house, or amount of this house + the max so far till n-2
# init the 0 to nums 0 and 1 to max of nums 0 or 1 because if we only have 2 houses we can chose to pick the more loaded one.
class Solution(object):
def rob(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
if len(nums) < 2:
return nums[0]
money = [0] * len(nums)
money[0] = nums[0]
money[1] = max(nums[1], nums[0])
for n in range(2, len(money)):
money[n] = max(money[n-1], money[n-2] + nums[n])
return money[-1]
- House Robber II
Solved
Medium
Topics
Companies
Hint
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3]
Output: 3
Constraints:
1 <= nums.length <= 100 0 <= nums[i] <= 1000
https://leetcode.com/problems/house-robber-ii/
Run house robber 198 on the list twice first, without 1st element and then without last element, return their max.
class Solution(object):
def rob(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
if len(nums) < 2:
return nums[0]
def solve(input):
if len(input) < 2:
return input[0]
amount = [0] * len(input)
amount[0] = input[0]
amount[1] = max(input[1], input[0])
for i in range(2, len(amount)):
amount[i] = max(amount[i-1], amount[i-2] + input[i])
return amount[-1]
return max(solve(nums[:-1]), solve(nums[1:]))
- Longest Palindromic Substring
Medium
Topics
Companies Amazon, Google
Given a string s, return the longest
palindromic
substring
in s.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Constraints:
1 <= s.length <= 1000 s consist of only digits and English letters.
https://leetcode.com/problems/longest-palindromic-substring/description/
2D array, mark true if palindrome exists from that point outwards.
Check from center outwards
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
ans = (0,0)
ans_len = 1
def palin(i,j):
while i > 0 and j < n-1 and s[i-1] == s[j+1]:
i -= 1
j += 1
return (i, j)
for i in range(0, n-1):
# odd
(a,b) = palin(i,i)
if (b-a+1) > ans_len:
ans_len = b-a+1
ans = (a,b)
if s[i] == s[i+1]:
(c,d) = palin(i,i+1)
if (d-c+1) > ans_len:
ans_len = d-c+1
ans = (c,d)
return s[ans[0]:ans[1]+1]
Dynamic Programming
# start with diff = 2 and go upwards#
eg. compare 0 and 1 if they are equlal check the previous element from 0 and 1 if they are palindrome
eg abllb at diff = 3 , ll is true (2,3) and i = 1
s[i] = b , s[i+diff] =b
dp[i+1][i-diff-1] is true (L,L is a palindrome)
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
dp = [[False] * n for i in range(n)]
ans = (0,0)
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
ans = (i, i+1)
for diff in range(2, n):
for i in range(0, n-diff):
j = i + diff
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
ans = (i, j)
return s[ans[0]:ans[1] + 1]
- Palindromic Substrings
Solved
Medium
Topics
Companies
Hint
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Constraints:
1 <= s.length <= 1000 s consists of lowercase English letters.
https://leetcode.com/problems/palindromic-substrings/description/
class Solution(object):
def countSubstrings(self, s):
“””
:type s: str
:rtype: int
“””
n = len(s)
palins = 0
def palin(i,j):
palins = 1
while (i > 0 and j < len(s) - 1) and s[i-1] == s[j+1]:
i -= 1
j += 1
palins += 1
return palins
for start in range(0, n-1):
# odd
odd = palin(start, start)
palins += odd
if s[start] == s[start+1]:
even = palin(start, start+1)
palins += even
return palins + 1
using the same DP as Q5
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for i in range(n)]
palins = 0
for i in range(n):
dp[i][i] = True
palins += 1
for i in range(n-1):
if s[i] == s[i+1]:
palins += 1
dp[i][i+1] = True
for diff in range(2, n):
for i in range(0, n-diff):
j = i+diff
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
palins += 1
return palins
- Decode Ways
Solved
Medium
Topics
Companies
A message containing letters from A-Z can be encoded into numbers using the following mapping:
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:
"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = “12”
Output: 2
Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).
Example 2:
Input: s = “226”
Output: 3
Explanation: “226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).
Example 3:
Input: s = “06”
Output: 0
Explanation: “06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”).
Constraints:
1 <= s.length <= 100 s contains only digits and may contain leading zero(s).
https://leetcode.com/problems/decode-ways/description/
Start from the end,
11106
dp will look somewhat like
[0, 0, 0, 0, 0, 1, 0]
The second last element will be the ways to arrange the last element.
For every element we move back, we check
a) If its 0 then we mark its place as zero (n1)
b) if it, and its next element combined make a number between 10-26, if so we take the n+1 and n+2 as the value at that otherwise just n+1’s value.
This is because if eg. number was 52834,
for element 2 we have 2 choices either pick 2 and dp at 8 or 28 + dp at 3 since 28 is invalid we just use the DP at 8.
Here n1 = n+1
n2 = n+2 to save space
otherwise you can create an array of len(n+1)
with element at n = 1.
class Solution:
def numDecodings(self, s: str) -> int:
# DP bottom up
n1 = 1
n2 = 0
n = len(s)
digits = set(["0","1","2","3","4","5","6"])
res = 0
for i in range(n-1, -1, -1):
if s[i] == "0":
n1,n2 = 0, n1
continue
if (i < n-1 and (s[i] == '1' or (s[i] == '2' and s[i+1] in digits))):
n1, n2 = n1 + n2, n1
else:
n1, n2 = n1, n1
return n1
Other solution goes from front to back.
~~~
class Solution:
def numDecodings(self, s: str) -> int:
# Array to store the subproblem results
dp = [0 for _ in range(len(s) + 1)]
dp[0] = 1
# Ways to decode a string of size 1 is 1. Unless the string is '0'.
# '0' doesn't have a single digit decode.
dp[1] = 0 if s[0] == "0" else 1
for i in range(2, len(dp)):
# Check if successful single digit decode is possible.
if s[i - 1] != "0":
dp[i] = dp[i - 1]
# Check if successful two digit decode is possible.
two_digit = int(s[i - 2 : i])
if two_digit >= 10 and two_digit <= 26:
dp[i] += dp[i - 2]
return dp[len(s)] ~~~ Same as above but O(1) memory ~~~ class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
f0 = 1
f1 = 0 if s[0] == "0" else 1
for i in range(2, len(s)+1):
temp = 0
if s[i-1] != "0":
temp = f1
if 10 <= int(s[i-2:i]) < 27:
temp += f0
f0,f1 = f1, temp
return f1 ```
Neetcode Solution
~~~
class Solution:
def numDecodings(self, s: str) -> int:
dp = {len(s):1}
def backtrack(i):
if i in dp:
return dp[i]
if s[i]=='0':
return 0
if i==len(s)-1:
return 1
res = backtrack(i+1)
if int(s[i:i+2])<27:
res+=backtrack(i+2)
dp[i]=res
return res
return backtrack(0) ~~~
Neetcode without recursion
class Solution:
def numDecodings(self, s: str) -> int:
dp = { len(s) : 1}
for i in range(len(s) -1 , -1, -1):
if s[i] == '0':
dp[i] = 0
else:
dp[i] = dp[i + 1]
if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] in "0123456")):
dp[i] = dp[i] + dp[i + 2]
return dp[0]
- Coin Change
Solved
Medium
Topics
Companies
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
https://leetcode.com/problems/coin-change/description/
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
coins = sorted(coins)
dp = [0] * (amount + 1)
for i in range(1, amount+1):
c = 0
mins = float(‘inf’)
while c < len(coins) and coins[c] <= i:
mins = min(mins, dp[i-coins[c]] + 1)
c += 1
dp[i] = mins
return -1 if dp[amount] == float(‘inf’) else dp[amount]
- Maximum Product Subarray
Solved
Medium
Topics
Companies
Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104 -10 <= nums[i] <= 10 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
https://leetcode.com/problems/maximum-product-subarray/description/
The key here is to keep track of min so far and max so far.
# reason being, min can be flipped to max with a negative number in the future.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
max_so_far = nums[0]
min_so_far = nums[0]
max_total = nums[0]
for i in range(1, len(nums)):
cur = nums[i]
max_so_far, min_so_far = max(cur, cur * max_so_far, cur * min_so_far), min(cur, cur * max_so_far, cur * min_so_far)
max_total = max(max_so_far, max_total)
return max_total
- Word Break
Solved
Medium
Topics
Companies
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:
Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: false
Constraints:
1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique.
https://leetcode.com/problems/word-break/description/
bottom up, start from the end and work way up. Similar to longest word without using banned characters.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[-1] = True
wordDict = set(wordDict)
for i in range(n-1, -1, -1):
for j in range(i, n+1):
if dp[j] and s[i:j] in wordDict:
dp[i] = True
return dp[0]
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[-1] = True
wordDict = set(wordDict)
for i in range(n-1, -1, -1):
for j in range(n, i, -1):
if dp[j] and s[i:j] in wordDict:
dp[i] = True
return dp[0]
Using Trie
from collections import defaultdict
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
Trie = lambda: defaultdict(Trie)
trie = Trie()
for word in wordDict:
cur = trie
for c in word:
cur = cur[c]
cur["$"] = True
n = len(s)
dp = [False] * (n+1)
dp[n] = True
for i in range(n-1, -1, -1):
cur = trie
for j in range(i, n):
if s[j] not in cur:
break
cur = cur[s[j]]
if cur["$"] == True and dp[j+1] == True:
dp[i] = True
break
return dp[0]
- Word Break II
Hard
Companies: Facebook 2024
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
Output: [“cats and dog”,”cat sand dog”]
Example 2:
Input: s = “pineapplepenapple”, wordDict = [“apple”,”pen”,”applepen”,”pine”,”pineapple”]
Output: [“pine apple pen apple”,”pineapple pen apple”,”pine applepen apple”]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: []
Constraints:
1 <= s.length <= 20 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 10 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique. Input is generated in a way that the length of the answer doesn't exceed 105.
https://leetcode.com/problems/word-break-ii/
from functools import cache, reduce
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
output = []
maxLen = reduce(lambda mlen,x: max(len(x), mlen), wordDict, 0)
wordDict = set(wordDict)
@cache
def rec(i):
if i == len(s):
return [""]
out = []
for j in range(i+1, min(i+maxLen, len(s))+1):
word = s[i:j]
if word in wordDict:
ret = rec(j)
for subwords in ret:
if subwords:
out.append(" ".join([word, subwords]))
else:
out.append(word)
return out
return rec(0)
O(n2^n), 2^n
- Longest Increasing Subsequence
Solved
Medium
Topics
Companies Amazon, Google
Given an integer array nums, return the length of the longest strictly increasing
subsequence
.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500 -104 <= nums[i] <= 104
Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
https://leetcode.com/problems/longest-increasing-subsequence/description/
DP n^2 Solution
Start from the end and begin building the memory
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
seq = [nums[0]]
n = len(nums)
for num in nums[1:]:
i = 0
while i < len(seq) and num > seq[i]:
i += 1
if i + 1 > len(seq):
seq.append(num)
else:
seq[i] = num
return len(seq)
N^2 solution no DP, Build the sequence likea monotonic increasing stack.
BUT instead of going from the top, start from the bottom, and if you see a value smaller than this value, replace it with the incming value.
THIS wont result in a correct sequence BUT will result in the correct count, as the size of sequence will only grow if we see value larger than largest. even if the middle valuesare incorrect, we know there are values smaller than the largest in the past.
eg.
9,10,2,100, 5
seq is 9, 10, 100
9
9, 10
2, 10
2, 10, 100
2, 5, 100 <– this is incorrect sequence BUT the length is still valid.
to get correct sequence you can’t use this method.
This method can be optimized by using binary search in the sequence to find insertion point.
thus making it nLogn
The nLog(n) Solution
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
seq = [nums[0]]
n = len(nums)
for num in nums[1:]:
if num > seq[-1]:
seq.append(num)
else:
insertion_point = bisect.bisect_left(seq, num)
seq[insertion_point] = num
return len(seq)
- Partition Equal Subset Sum
Solved
Medium
Topics
Companies
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 200 1 <= nums[i] <= 100
https://leetcode.com/problems/partition-equal-subset-sum/description/
Create a set of sums with the last value in the nums
Run through all values except last one from back to start
Then to the set add all the values with the sum of current value + values in set.
This is the same as building combinations for all n i.e from 1Cn to nCn.
eg 1345
1, 2, 3, 4
12, 13, 14, 23, 24, 34
123, 124, 134, 234
1234
class Solution(object):
def canPartition(self, nums):
“””
:type nums: List[int]
:rtype: bool
“””
sums = set()
sums.add(nums[-1])
n = len(nums)
total_sum = sum(nums)
if total_sum % 2:
return False
target = total_sum // 2
for i in range(n-2, -1, -1):
tset = sums.copy()
for n in tset:
sums.add(nums[i] + n)
if target in sums:
return True
return target in sums
DP – dont like this much but good to talk about in interview
class Solution:
def canPartition(self, nums: List[int]) -> bool:
@lru_cache(maxsize=None)
def dfs(nums, target, idx):
if target == 0:
return True
if idx == 0 or target < 0:
return False
return dfs(nums, target - nums[idx-1], idx-1) or dfs(nums, target, idx-1)
total_sum = sum(nums)
if total_sum % 2:
# Odd sum cant split evenly
return False
target = total_sum // 2
n = len(nums)
return dfs(tuple(nums), target, n-1)
