Best Time to Buy and Sell Stock | A Compilation of Solutions
Best Time to Buy and Sell Stock is a popular series of problems on LeetCode. In this compilation, I will present to you the solutions to ALL of the problems – using just ONE approach. That’s right, just one approach.
0. Problem List (Order of Solving)
- 122. Best Time to Buy and Sell Stock II
- 309. Best Time to Buy and Sell Stock with Cooldown
- 714. Best Time to Buy and Sell Stock with Transaction Fee
- 121. Best Time to Buy and Sell Stock
- 123. Best Time to Buy and Sell Stock III
- 188. Best Time to Buy and Sell Stock IV
1. Best Time to Buy and Sell Stock: Invariants & Setup
1.1. I/O Format
1.2. Constraints
There are only two constraints common across all the problems:
- actions available: buy, sell, hold
- note that hold action is not explicitly mentioned, but we have to include it ourselves
- stock = 0/1
- in all the questions, we can never have more than 1 stocks in our inventory/portfolio
2. Best Time to Buy and Sell Stock: Core Logic
2.1. Simulation
At each point of time, we have 3 decisions that I can make.
At time = 0
- At this time, we don’t have any stocks beforehand, so we can not sell
- We can only buy or hold
At time = 1
- We can either sell or hold
- We can’t buy, since we already have 1 stock in the portfolio
At time = 2
- Since we sold the stock, we can either buy a new stock
- or, we can take a holiday (hold) our position
2.2. Recursion
There are a couple of things happening:
- Depending upon the time & stock status, we can take 2 of the 3 actions
- Since we don’t know which of them is going to pan out better in the future – so we need a way to look into the future to tell us what to do
- This is where recursion can help us – the ability of seeing into the future and seeing what decision played out well
3. Best Time to Buy and Sell Stock: Code: II/Cooldown/Fee
122. Best Time to Buy and Sell Stock II
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def recurse(i, stock):
if i >= n: return 0
buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+1, 0)) if stock == 1 else -inf
hold = recurse(i+1, stock)
return max(buy, sell, hold)
n = len(prices)
return recurse(0, 0)
309. Best Time to Buy and Sell Stock with Cooldown
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
@lru_cache(None)
def recurse(i, stock):
if i >= n: return 0
buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
sell = (prices[i]-fee + recurse(i+1, 0)) if stock == 1 else -inf # ONLY line changed
hold = recurse(i+1, stock)
return max(buy, sell, hold)
n = len(prices)
return recurse(0, 0)
714. Best Time to Buy and Sell Stock with Transaction Fee
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def recurse(i, stock):
if i >= n: return 0
buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+2, 0)) if stock == 1 else -inf # only line changed
hold = recurse(i+1, stock)
return max(buy, sell, hold)
n = len(prices)
return recurse(0, 0)
4. Transaction Modifications
For the rest of the problems “Best Time to Buy and Sell Stock” I/III/IV, we have modify the code a slight bit.
- Up till now, we could do as many transactions as we pleased. But for these cases, we have to somehow restrict the number of transactions we can make
- We add count as the third parameter
5. Best Time to Buy and Sell Stock: Code: I/III/IV
121. Best Time to Buy and Sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def recurse(i, stock, count):
if i >= n: return 0
if count >= k: return 0
buy = (-prices[i] + recurse(i+1, 1, count)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+1, 0, count+1)) if stock == 1 else -inf
hold = recurse(i+1, stock, count)
return max(buy, sell, hold)
n = len(prices)
k = 1 # set number of transactions here
return recurse(0, 0, 0)
123. Best Time to Buy and Sell Stock III
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@lru_cache(None)
def recurse(i, stock, count):
if i >= n: return 0
if count >= k: return 0
buy = (-prices[i] + recurse(i+1, 1, count)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+1, 0, count+1)) if stock == 1 else -inf
hold = recurse(i+1, stock, count)
return max(buy, sell, hold)
n = len(prices)
k = 2 # set number of transactions here
return recurse(0, 0, 0)
188. Best Time to Buy and Sell Stock IV
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# number of transactions already provided as input
@lru_cache(None)
def recurse(i, stock, count):
if i >= n: return 0
if count >= k: return 0
buy = (-prices[i] + recurse(i+1, 1, count)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+1, 0, count+1)) if stock == 1 else -inf
hold = recurse(i+1, stock, count)
return max(buy, sell, hold)
n = len(prices)
return recurse(0, 0, 0)
6. Conclusion
We saw how to approach the problem using the ideas of recursion. Then saw the amount of similarity between the problems, and coded up a generic recursive solution that can solve all of them with ease. We had to make some slight modifications here and there, but the end result was getting Accepted in all of the 6 problems.
If you have made it this far, thanks a lot for reading 🙂
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022