NUHMAN.com

Introduction

LeetCode 309: Best Time to Buy and Sell Stock with Cooldown is an extension of the Best Time to Buy and Sell Stock problem, but with an additional cooldown period after a sell. In this problem, you are given an array representing the prices of a stock on different days. You can buy and sell the stock at most once per day, but after you sell the stock, you must wait for one day (cooldown) before making another transaction.

The challenge is to determine the maximum profit you can achieve while adhering to the cooldown rule. This can be solved efficiently using dynamic programming.

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You are allowed to complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times), but you must pay a cooldown period after selling the stock, meaning you cannot buy on the next day after you sell.

Return the maximum profit you can achieve.

Note:

• You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
• After you sell, you must wait one day before you can buy again.

Example

python

# Example 1
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: 
- Buy on day 0 (price = 1), sell on day 2 (price = 3), profit = 3-1 = 2.
- Cooldown on day 3.
- Buy on day 4 (price = 2), sell on day 4 (price = 2), profit = 3.
So, the maximum profit is 3.

# Example 2
Input: prices = [1]
Output: 0
Explanation: No transactions are done, so the maximum profit is 0.

Step-by-Step Solution

🧠 Intuition

The key to solving this problem is recognizing that after a sell, there is a cooldown period, which prevents buying the stock the very next day. The dynamic programming (DP) approach can be used to solve this problem efficiently by maintaining states for:

• Holding a stock.
• Not holding a stock, where the last operation was either selling or cooling down.

✅ Approach

We can break down the problem into the following states:

1. Sell: The profit after selling the stock.
2. Buy: The profit after buying the stock.
3. Cooldown: The profit during a cooldown period.

We will use three variables (sell, buy, cooldown) to track the maximum profit at any given day for each of the above states.

State Transitions:

• Sell: On any given day, you can sell the stock if you had bought it on any previous day or if you are in a cooldown state.
• sell = buy + prices[i]
• Buy: On any given day, you can buy the stock if you were in a cooldown state from the previous day or if you were in the previous buy state.
• buy = max(buy, cooldown - prices[i])
• Cooldown: On any given day, you can be in a cooldown state either from the previous cooldown or after selling the stock.
• cooldown = max(cooldown, sell)

The final result will be the maximum profit at the end of the array, which will be in the sell or cooldown state.

✅ Python Code

python

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # Initial state: no stock, no profit
        sell, buy, cooldown = 0, -prices[0], 0
        
        for price in prices[1:]:
            # Update the states
            new_sell = buy + price  # If we sell today
            new_buy = max(buy, cooldown - price)  # Max profit if we buy today
            new_cooldown = max(cooldown, sell)  # Max profit if we cooldown today
            
            sell, buy, cooldown = new_sell, new_buy, new_cooldown
        
        return max(sell, cooldown)

Explanation of the Code

1. Initialization:

• sell = 0: The maximum profit if we don't have any stock (i.e., we have already sold).
• buy = -prices[0]: The maximum profit if we buy the stock on the first day. We store the negative of the first price because we are spending money to buy the stock.
• cooldown = 0: The maximum profit if we are in a cooldown period, which is initially 0.

1. Loop through each price:

• For each price in the list starting from the second day, we update the states:
• new_sell = buy + price: If we sell today, we add the profit from the previous buy state and the price on the current day.
• new_buy = max(buy, cooldown - price): We update the buy state by either keeping the previous buy state or buying today (from the cooldown state).
• new_cooldown = max(cooldown, sell): The cooldown state is either the previous cooldown or the state where we just sold.
• Then, update the sell, buy, and cooldown variables for the next iteration.

1. Return the result:

• The maximum profit after the final day will be the greater of sell or cooldown.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: The algorithm processes each price exactly once, so the time complexity is O(n), where n is the number of days (or the length of the prices array).
• Space Complexity: We use only a constant amount of space for the sell, buy, and cooldown variables, so the space complexity is O(1).

🔍 Edge Cases

1. Empty Input:

• If the input list prices is empty, return 0 as no transactions can be made.

1. Single Day:

• If there is only one day, you can't sell or buy, so the maximum profit is 0.

1. Decreasing Prices:

• If the prices are strictly decreasing, the maximum profit will still be 0 because no profitable transaction is possible.

1. All Prices Same:

• If all prices are the same, no transaction will result in a profit, so the maximum profit is 0.

✅ Conclusion

LeetCode 309: Best Time to Buy and Sell Stock with Cooldown introduces a cooldown restriction after selling the stock. By using dynamic programming, we can efficiently compute the maximum profit with states for buying, selling, and cooling down. The solution runs in linear time, making it suitable for large inputs.