# 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.

## 1. Best Time to Buy and Sell Stock: Invariants & Setup

### 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 We can either buy a new stock or hold the previous position – take a holiday (hold).

### 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)

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)

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)

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

```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)

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)

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)

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 🙂

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.