LeetCode 309: Best Time to Buy and Sell Stock with Cooldown Solution in Python – A Step-by-Step Guide

What Is LeetCode 309: Best Time to Buy and Sell Stock with Cooldown?

In LeetCode 309: Best Time to Buy and Sell Stock with Cooldown, you’re given an array of stock prices where prices[i] is the price on day i. Your goal is to maximize profit through buying and selling, with these rules: you can’t buy and sell on the same day, and after selling, you must wait one day (a “cooldown”) before buying again. For example, with prices [1, 2, 3, 0, 2], the best profit is 3 (buy at 1, sell at 3, cooldown, buy at 0, sell at 2). This problem builds on classics like LeetCode 122: Best Time to Buy and Sell Stock II, adding the cooldown twist.

Problem Statement

• Input: An integer array prices representing daily stock prices.
• Output: An integer—the maximum possible profit.
• Rules:
• Buy before sell.
• One share at a time.
• Cooldown of 1 day after selling before buying again.

Constraints

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

Examples

• Input: [1, 2, 3, 0, 2]
• Output: 3 (Buy at 1, sell at 3, cooldown, buy at 0, sell at 2)
• Input: [1]
• Output: 0 (No profit possible)
• Input: [2, 1]
• Output: 0 (Price decreases, no profit)

Understanding the Problem: Trading with a Cooldown

To solve LeetCode 309: Best Time to Buy and Sell Stock with Cooldown in Python, we need a method to track decisions—buy, sell, or rest—while respecting the cooldown. A naive approach might try all possible trades recursively, but that’s exponential in time. Instead, we’ll use dynamic programming:

• Best Solution (Optimized DP): O(n) time, O(1) space—three variables for states.
• Alternative Solution (Detailed DP): O(n) time, O(n) space—array-based states.

Let’s start with the optimized DP, explained in a way that’s easy to grasp.

Best Solution: Optimized Dynamic Programming with Three States

Why This Is the Best Solution

The optimized DP approach is the top choice for LeetCode 309 because it’s both efficient—O(n) time, O(1) space—and intuitive once you see the states in action. It tracks three key scenarios at each day: holding a stock, not holding after selling (post-cooldown), and not holding before selling (ready to buy). By updating these states iteratively, it avoids redundant calculations and memory overhead. It’s like a trader’s notepad—lean and smart!

How It Works

Think of your trading status each day:

• Hold: You’re holding a stock (bought it earlier or today).
• Sold: You just sold today (post-sell, in cooldown).
• Rest: You’re not holding and can buy (post-cooldown or never bought).
• Step 1: Define Transitions:
• Hold: Either keep holding or buy today (from Rest).
• Sold: Sell today (from Hold).
• Rest: Either stay resting or move from Sold (cooldown over).
• Step 2: Update States:
• Use previous day’s values to compute today’s max profit.
• Step 3: Why It Works:
• Captures all possibilities with minimal variables.
• Cooldown enforced by state dependencies.

It’s like juggling three balls—hold, sell, rest—day by day!

Step-by-Step Example

Example: prices = [1, 2, 3, 0, 2]

• Day 0 (1):
• Hold = -1 (buy at 1), Sold = 0 (can’t sell yet), Rest = 0.
• Day 1 (2):
• Hold = max(-1, 0-2) = -1, Sold = -1+2 = 1, Rest = 0.
• Day 2 (3):
• Hold = max(-1, 0-3) = -1, Sold = -1+3 = 2, Rest = 1.
• Day 3 (0):
• Hold = max(-1, 1-0) = 1, Sold = -1+0 = -1, Rest = 2.
• Day 4 (2):
• Hold = max(1, 2-2) = 1, Sold = 1+2 = 3, Rest = 2.
• Result: Max(Sold, Rest) = 3.

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        # Initialize states
        hold = -prices[0]  # Profit if holding after buying at day 0
        sold = 0           # Profit if just sold (none yet)
        rest = 0           # Profit if resting (no action)

        # Iterate through days
        for i in range(1, len(prices)):
            # Previous states
            prev_hold = hold
            prev_sold = sold
            prev_rest = rest
            # Update states
            hold = max(prev_hold, prev_rest - prices[i])  # Keep or buy
            sold = prev_hold + prices[i]                  # Sell today
            rest = max(prev_rest, prev_sold)              # Rest or post-sell

        # Max profit is either after selling or resting
        return max(sold, rest)

• Lines 3-4: Handle edge case—need at least 2 days.
• Lines 6-8: Day 0: Buy (-price), no sell/rest yet.
• Lines 11-17: Loop:
• Store previous states.
• Hold: Max of keep holding or buy from rest.
• Sold: Sell held stock.
• Rest: Max of stay resting or post-sell.
• Line 19: Return max profit.
• Time Complexity: O(n)—one pass.
• Space Complexity: O(1)—three variables.

This is like a trader’s quick checklist—fast and efficient!

Alternative Solution: Detailed Dynamic Programming with Arrays

Why an Alternative Approach?

The detailed DP approach uses arrays to track states—O(n) time, O(n) space. It’s more explicit, showing profit for each state at every day, making it easier to visualize but less space-efficient. It’s like a full trading log—great for learning!

How It Works

Define states for each day:

• dp[i][0]: Max profit holding stock at day i.
• dp[i][1]: Max profit after selling (in cooldown).
• dp[i][2]: Max profit resting (can buy).
• Transitions:
• Hold: Keep holding or buy from rest two days ago.
• Sold: Sell from hold.
• Rest: Stay resting or post-sell.

Step-by-Step Example

Example: prices = [1, 2, 3]

• Day 0: dp[0] = [-1, 0, 0]
• Day 1: dp[1] = [-1, 1, 0]
• Day 2: dp[2] = [-1, 2, 1]
• Result: Max(dp[2][1], dp[2][2]) = 2.

Code for Detailed DP Approach

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        n = len(prices)
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = -prices[0]  # Hold on day 0

        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])  # Hold
            dp[i][1] = dp[i-1][0] + prices[i]                   # Sell
            dp[i][2] = max(dp[i-1][2], dp[i-1][1])              # Rest

        return max(dp[n-1][1], dp[n-1][2])

• Time Complexity: O(n)—one pass.
• Space Complexity: O(n)—DP array.

It’s a detailed profit tracker!

Comparing the Two Solutions

• Optimized DP (Best):
• Pros: O(n) time, O(1) space, concise.
• Cons: Less explicit.
• Detailed DP (Alternative):
• Pros: O(n) time, O(n) space, clear states.
• Cons: More memory.

Optimized DP wins for efficiency.

Additional Examples and Edge Cases

• [1, 2]: 1 (Buy 1, sell 2).
• [3, 2, 1]: 0 (No profit).
• [1, 2, 4]: 3 (Buy 1, sell 4).

Both handle these perfectly.

Complexity Breakdown

• Optimized DP: Time O(n), Space O(1).
• Detailed DP: Time O(n), Space O(n).

Optimized is leaner.

Key Takeaways

• Optimized DP: Three states—smart and fast!
• Detailed DP: Full log—clear and educational!
• Python: Loops and logic shine—see [Python Basics](/python/basics).
• Trading: Cooldown adds strategy.

Final Thoughts: Maximize Your Trades

LeetCode 309: Best Time to Buy and Sell Stock with Cooldown in Python is a dynamic trading puzzle. The optimized DP offers speed and simplicity, while the detailed DP provides clarity. Want more stock challenges? Try LeetCode 122: Best Time to Buy and Sell Stock II or LeetCode 714: Best Time to Buy and Sell Stock with Transaction Fee. Ready to trade? Head to Solve LeetCode 309 on LeetCode and cash in today!