Best Time to Buy and Sell Stock with Cooldown | Solution Explained

LeetCode 309. Best Time to Buy and Sell Stock with Cooldown. I solve this problem using recursion. Solution explained in detail. Problem Link.

Problem Discussion

We are given the input as an array, and we have to return the maximum profit possible.

The solution:

As other people have pointed out, it can feel like a hard level problem. However, I have an explanation for Best Time to Buy and Sell Stock that you’ll love.

Observations

As always, whenever confused, I suggest to look at a couple of basic examples, and see if you can find things out.

• prices = [1], answer = 0. The only operation is hold at this point, since you can never sell. For all len(prices) == 1, answer is 0
• prices = [1,2], answer = 1. In this case, we can either hold out the entire time and get a profit of 0, or, we can buy at time = 0 and sell at time = 1 getting us a profit of 1.
• prices = [1,2,3], answer = 2. This is where things get more interesting. In this case, we somehow need the information of holding out at time = 1 instant. We want to look into the future, saying that perhaps we should wait for the stock price to increase.

Thus, we realize that we want to look into the future. If you have been following me, you know its the cue for recursion.

Recursion

• return type: Its clear that we want the recursion to tell us what the profits are, since that is the goal.
• base case: the recursion ends when time/index >= n, the length of the array
• inputs to recursion: index & stock
  • index: tells us what time it is right now
  • stock: a binary 0/1 telling us the amount of stock we have
• to look into the future, we have 3 cases
  • buy: if stock = 0, take the cost of prices[i] right now, and set the stock = 1
  • sell: if the stock = 1 previously, we can sell it for a profit of prices[i] and skip the next time step
  • hold: do nothing, just look at the next index.

Best Time to Buy and Sell Stock with Cooldown: Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1: return 0
        
        @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
            hold = recurse(i+1, stock)
            return max(buy, sell, hold)
        
        n = len(prices)
        return recurse(0, 0)

Best Time to Buy and Sell Stock with Cooldown: Code (Without LRU Cache)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1: return 0
        
        def recurse(i, stock):
            if i >= n: return 0

            if dp[i][stock] != -inf: return dp[i][stock] # line added        

            buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
            sell = (prices[i] + recurse(i+2, 0)) if stock == 1 else -inf
            hold = 0 + recurse(i+1, stock)
            
            dp[i][stock] = max(buy, sell, hold) # line added
            return dp[i][stock]
        
        n = len(prices)
        dp = [[-inf, -inf] for _ in range(n+1)] # initializing dp
        return recurse(0, 0)

Tanishq Chaudhary

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