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)

Dependency Graph of “Best Time to Buy and Sell Stock” series

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

1.1. I/O Format

Best Time to Buy and Sell Stock: IO Format
Best Time to Buy and Sell Stock: IO 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.

we have to make decisions to buy/sell/hold at each point in time
we have to make decisions to buy/sell/hold at each point in time

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
after making the first decision to buy, we have 1 stocks in the portfolio & option to sell & hold. NOT buy.
after making the first decision to buy, we have 1 stocks in the portfolio & option to sell & hold. NOT buy.

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).
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)
            
            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 🙂

    Leave a Reply

    Your email address will not be published. Required fields are marked *