Best Time to Buy and Sell Stock with Cooldown

Difficulty: Medium Source: NeetCode

Problem

You are given an array prices where prices[i] is the price of a stock on day i. You can buy and sell on multiple days, but you cannot buy on the next day after selling (cooldown of 1 day). You may not hold more than one stock at a time. Find the maximum profit.

Example 1: Input: prices = [1, 2, 3, 0, 2] Output: 3 Explanation: Buy on day 0, sell on day 1, cooldown on day 2, buy on day 3, sell on day 4.

Example 2: Input: prices = [1] Output: 0

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• State Machine DP — tracking multiple mutually exclusive states
• Buy and Sell Stock I/II — simpler versions without cooldown

1. Brute Force / Recursive

Intuition

At each day we are in one of three states: holding a stock, in cooldown (just sold), or idle (no stock, not cooling down). We recurse through each day, trying every valid transition from the current state. This explores all possible buy/sell schedules but is exponential without memoization.

Algorithm

1. Define dfs(i, holding) = max profit from day i onwards, given whether we currently hold a stock.
2. Base case: i >= len(prices) → return 0.
3. If holding:
   • Sell today: profit = prices[i] + dfs(i+2, False) (skip day i+1 for cooldown)
   • Hold: dfs(i+1, True)
   • Return max of these.
4. If not holding:
   • Buy today: -prices[i] + dfs(i+1, True)
   • Skip: dfs(i+1, False)
   • Return max of these.

Solution

def maxProfit(prices):
    def dfs(i, holding):
        if i >= len(prices):
            return 0
        if holding:
            sell = prices[i] + dfs(i + 2, False)
            hold = dfs(i + 1, True)
            return max(sell, hold)
        else:
            buy = -prices[i] + dfs(i + 1, True)
            skip = dfs(i + 1, False)
            return max(buy, skip)

    return dfs(0, False)


print(maxProfit([1, 2, 3, 0, 2]))  # 3
print(maxProfit([1]))              # 0
print(maxProfit([2, 1]))           # 0

Complexity

• Time: O(2^n) — exponential without memoization
• Space: O(n) — recursion depth

2. DP with State Machine

Intuition

Model the problem as a state machine with three states at each day:

• holding: currently holding a stock
• sold (cooldown): just sold, must wait one day
• idle: free to buy

Transitions:

• holding[i] = max(holding[i-1], idle[i-1] - prices[i]) — keep holding, or buy from idle
• sold[i] = holding[i-1] + prices[i] — sell what we hold
• idle[i] = max(idle[i-1], sold[i-1]) — stay idle, or come out of cooldown

The answer is max(sold[-1], idle[-1]) — we can’t end holding.

Algorithm

1. Initialise holding = -prices[0], sold = 0, idle = 0.
2. For each day from index 1:
   • new_holding = max(holding, idle - prices[i])
   • new_sold = holding + prices[i]
   • new_idle = max(idle, sold)
   • Update all three states simultaneously.
3. Return max(sold, idle).

Solution

def maxProfit(prices):
    if not prices:
        return 0

    holding = -prices[0]
    sold = 0
    idle = 0

    for i in range(1, len(prices)):
        new_holding = max(holding, idle - prices[i])
        new_sold = holding + prices[i]
        new_idle = max(idle, sold)
        holding, sold, idle = new_holding, new_sold, new_idle

    return max(sold, idle)


print(maxProfit([1, 2, 3, 0, 2]))  # 3
print(maxProfit([1]))              # 0
print(maxProfit([2, 1]))           # 0
print(maxProfit([6, 1, 3, 2, 4, 7]))  # 6

Complexity

• Time: O(n)
• Space: O(1) — only three variables needed

Common Pitfalls

Updating states in place without temporaries. If you do holding = max(holding, idle - prices[i]) then immediately use the new holding to compute sold, you’ll get wrong results. Always compute all three new values before assigning.

Skipping two days instead of one. The cooldown is exactly 1 day — you sell on day i and can next buy on day i+2. In the recursive approach, jump to i+2 when selling, not i+3.

Including the holding state in the final answer. You can’t end the simulation while still holding a stock (you’d be sitting on unrealised profit). Only max(sold, idle) makes sense at the end.