Best Time to Buy and Sell Stock with Cooldown

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (buy one and sell one share multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
You may not engage in multiple transactions simultaneously (you must sell before you buy again).

This problem extends the classic "Buy and Sell Stock II" (unlimited transactions) by adding a cooldown constraint. The cooldown forces a gap between selling and the next purchase, creating an interesting optimization problem best modeled as a state machine with Dynamic Programming.

Examples

Example 1

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

Output: 3

Explanation: The optimal transactions are:

Day 0: Buy at price 1
Day 1: Sell at price 2 (profit = +1)
Day 2: Cooldown (mandatory after selling)
Day 3: Buy at price 0
Day 4: Sell at price 2 (profit = +2)

Total profit = 1 + 2 = 3

Note: Buying at 1 and selling at 3 (profit 2) is worse because you can't buy the dip at 0 due to cooldown.

Example 2

Input: prices = [1]

Output: 0

Explanation: Only one day — no transaction is possible. Maximum profit is 0.

Constraints

1 ≤ prices.length ≤ 5000
0 ≤ prices[i] ≤ 1000

Editorial

Brute Force - Recursion (Explore All Decisions)

Intuition

At each day, we face a decision based on our current state:

If we can buy (no stock held, not in cooldown): We either buy at today's price or skip to the next day.
If we're holding stock: We either sell at today's price (which triggers a 1-day cooldown) or hold and wait for a better price.

The brute force explores every possible combination of buy/sell/hold/skip decisions across all days. At each day we branch into 2 choices, creating a recursion tree that grows exponentially.

Think of it like standing at a crossroads every morning: "Should I buy?" or "Should I sell?" or "Should I wait?" Brute force walks down every possible path and picks the one with the highest profit.

Step-by-Step Explanation

Let's trace the optimal path through prices = [1, 2, 3, 0, 2] that the recursion would discover:

Step 1: Day 0, state = canBuy. Price = 1. Choose to BUY. Spend 1.

Step 2: Day 1, state = holding. Price = 2. Choose to SELL. Gain 2. Profit so far = 2 - 1 = 1.

Step 3: Day 2, state = cooldown. Price = 3. FORCED to rest — can't buy the day after selling.

Step 4: Day 3, state = canBuy. Price = 0. Choose to BUY. Spend 0. (Great deal!)

Step 5: Day 4, state = holding. Price = 2. Choose to SELL. Gain 2. Profit = 1 + (2 - 0) = 3.

Step 6: End of array. Total profit = 3.

Step 7: But brute force doesn't just try this path — it tries ALL paths: skipping day 0, buying day 1 instead, holding through to day 2, etc. Each branching doubles the work.

Step 8: With 5 days and 2 choices per day, the recursion explores up to 2^5 = 32 paths. For n = 5000, that's 2^5000 — completely impractical.

Brute Force — Tracing the Optimal Recursive Path — Watch the recursion trace one path through all days, making buy/sell/cooldown decisions at each step. In reality, brute force explores ALL such paths.

Algorithm

Define solve(day, canBuy) returning max profit from day onwards
Base case: If day ≥ n, return 0 (no more trading days)
If canBuy = True:
- Option A: Buy → -prices[day] + solve(day + 1, False)
- Option B: Skip → solve(day + 1, True)
- Return max(A, B)
If canBuy = False (holding stock):
- Option A: Sell → prices[day] + solve(day + 2, True) (day+2 for cooldown)
- Option B: Hold → solve(day + 1, False)
- Return max(A, B)
Start with solve(0, True)

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return solve(0, true, prices);
    }

private:
    int solve(int day, bool canBuy, vector<int>& prices) {
        if (day >= (int)prices.size()) return 0;

        if (canBuy) {
            int buy = -prices[day] + solve(day + 1, false, prices);
            int skip = solve(day + 1, true, prices);
            return max(buy, skip);
        } else {
            int sell = prices[day] + solve(day + 2, true, prices);
            int hold = solve(day + 1, false, prices);
            return max(sell, hold);
        }
    }
};

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)

        def solve(day: int, can_buy: bool) -> int:
            if day >= n:
                return 0

            if can_buy:
                buy = -prices[day] + solve(day + 1, False)
                skip = solve(day + 1, True)
                return max(buy, skip)
            else:
                sell = prices[day] + solve(day + 2, True)
                hold = solve(day + 1, False)
                return max(sell, hold)

        return solve(0, True)

class Solution {
    public int maxProfit(int[] prices) {
        return solve(0, true, prices);
    }

    private int solve(int day, boolean canBuy, int[] prices) {
        if (day >= prices.length) return 0;

        if (canBuy) {
            int buy = -prices[day] + solve(day + 1, false, prices);
            int skip = solve(day + 1, true, prices);
            return Math.max(buy, skip);
        } else {
            int sell = prices[day] + solve(day + 2, true, prices);
            int hold = solve(day + 1, false, prices);
            return Math.max(sell, hold);
        }
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each day, the recursion branches into 2 choices (buy/skip or sell/hold). Without memoization, the same subproblems are solved repeatedly. The recursion tree grows exponentially — solve(2, False) might be called from multiple different parent calls, each recomputing the same result.

Space Complexity: O(n)

The recursion stack can go n levels deep (one level per day in the worst case). No additional data structures are used.

Why This Approach Is Not Efficient

The recursion has massive overlapping subproblems. For example, solve(2, False) ("holding stock on day 2, what's the best I can do?") gets called from multiple parent paths — once from buying on day 0 and holding through day 1, and again from buying on day 1 directly.

The total number of unique subproblems is only 2n — each (day, canBuy) pair, where day ranges from 0 to n-1 and canBuy is True or False. But the brute force recomputes these same subproblems exponentially many times.

If we simply cache (memoize) the result of each unique (day, canBuy) pair the first time we compute it, every subsequent call to the same subproblem becomes O(1). This transforms the exponential solution into a linear one.

Better Approach - Memoization (Top-Down DP)

Intuition

The structure of the recursion is perfect — it correctly models all valid trading sequences with cooldowns. The only problem is redundant work. Memoization fixes this by storing results in a lookup table.

We create a 2D memo table: memo[day][canBuy] where:

day ranges from 0 to n-1
canBuy is 0 (holding) or 1 (can buy)

Before computing solve(day, canBuy), we check the memo table. If the result is already cached, return it immediately. Otherwise, compute it, store it, and return.

This is like a student solving homework: the first time you encounter a problem, you work through it and write down the answer. If the same problem appears on the next page, you just look up your notes instead of re-deriving the solution.

Step-by-Step Explanation

Let's trace the memoization filling on prices = [1, 2, 3, 0, 2]:

The memo table has 2 rows (canBuy = True/False) and 5 columns (days 0-4). It fills right-to-left as the recursion resolves from the deepest calls first.

Step 1: Recursion dives deep. solve(4, F) = max(sell=2+0, hold=0) = 2. solve(4, T) = max(buy=-2+0, skip=0) = 0.

Step 2: solve(3, T) = max(buy=0+solve(4,F)=2, skip=solve(4,T)=0) = 2. solve(3, F) = max(sell=0+0, hold=solve(4,F)=2) = 2.

Step 3: solve(2, F) = max(sell=3+solve(4,T)=3, hold=solve(3,F)=2) = 3. Selling at price 3 beats holding.

Step 4: solve(1, F) = max(sell=2+solve(3,T)=4, hold=solve(2,F)=3) = 4. Selling at day 1 and buying at day 3 (the dip) is better!

Step 5: solve(2, T) = max(buy=-3+solve(3,F)=-1, skip=solve(3,T)=2) = 2. Buying at price 3 is too expensive.

Step 6: solve(1, T) = max(buy=-2+solve(2,F)=1, skip=solve(2,T)=2) = 2. Skipping day 1 is better than buying.

Step 7: solve(0, T) = max(buy=-1+solve(1,F)=3, skip=solve(1,T)=2) = 3. Buying at day 0 (price 1) is optimal!

Step 8: Return memo[0][T] = 3.

Memoization Table — Filling On-Demand via Recursion — Watch the memo table fill right-to-left as the recursion resolves deepest calls first. Each cell is computed once and reused — eliminating exponential redundancy.

Algorithm

Create a memo table: memo[n][2] initialized to -1 (uncomputed)
Define solve(day, canBuy) same as brute force, but:
- Before computing: if memo[day][canBuy] ≠ -1, return cached result
- After computing: store result in memo[day][canBuy]
Return solve(0, True)

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> memo(n, vector<int>(2, -1));
        return solve(0, 1, prices, memo);
    }

private:
    int solve(int day, int canBuy, vector<int>& prices, vector<vector<int>>& memo) {
        if (day >= (int)prices.size()) return 0;
        if (memo[day][canBuy] != -1) return memo[day][canBuy];

        if (canBuy) {
            int buy = -prices[day] + solve(day + 1, 0, prices, memo);
            int skip = solve(day + 1, 1, prices, memo);
            memo[day][canBuy] = max(buy, skip);
        } else {
            int sell = prices[day] + solve(day + 2, 1, prices, memo);
            int hold = solve(day + 1, 0, prices, memo);
            memo[day][canBuy] = max(sell, hold);
        }
        return memo[day][canBuy];
    }
};

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        memo = {}

        def solve(day: int, can_buy: bool) -> int:
            if day >= n:
                return 0
            if (day, can_buy) in memo:
                return memo[(day, can_buy)]

            if can_buy:
                buy = -prices[day] + solve(day + 1, False)
                skip = solve(day + 1, True)
                memo[(day, can_buy)] = max(buy, skip)
            else:
                sell = prices[day] + solve(day + 2, True)
                hold = solve(day + 1, False)
                memo[(day, can_buy)] = max(sell, hold)

            return memo[(day, can_buy)]

        return solve(0, True)

class Solution {
    private int[][] memo;

    public int maxProfit(int[] prices) {
        int n = prices.length;
        memo = new int[n][2];
        for (int[] row : memo) Arrays.fill(row, -1);
        return solve(0, 1, prices);
    }

    private int solve(int day, int canBuy, int[] prices) {
        if (day >= prices.length) return 0;
        if (memo[day][canBuy] != -1) return memo[day][canBuy];

        if (canBuy == 1) {
            int buy = -prices[day] + solve(day + 1, 0, prices);
            int skip = solve(day + 1, 1, prices);
            memo[day][canBuy] = Math.max(buy, skip);
        } else {
            int sell = prices[day] + solve(day + 2, 1, prices);
            int hold = solve(day + 1, 0, prices);
            memo[day][canBuy] = Math.max(sell, hold);
        }
        return memo[day][canBuy];
    }
}

Complexity Analysis

Time Complexity: O(n)

There are 2n unique states: (day, canBuy) for day ∈ [0, n-1] and canBuy ∈ {True, False}. Each state is computed exactly once and cached. Each computation does O(1) work (just comparisons and additions). Total: O(2n) = O(n).

Space Complexity: O(n)

The memo table stores 2n entries: O(n) space. The recursion stack can also be O(n) deep. Total space: O(n).

Why This Approach Is Not Efficient

Memoization gives us O(n) time — excellent! But we're using O(n) space for the memo table plus O(n) for the recursion stack.

Looking at the transition formulas more carefully, each day's states only depend on the previous day (and at most 2 days back for the cooldown). We don't need to store the entire table — we can compute values left-to-right using just a few variables.

The key insight is to reformulate the problem as a state machine with 3 states:

Hold: We own a stock
Sold: We just sold today (entering cooldown)
Rest: We don't own stock and are free to buy

Each state at day i depends only on the states at day i-1. We can use 3 variables instead of a 2D table, reducing space from O(n) to O(1).

Optimal Approach - State Machine DP (Space Optimized)

Intuition

Model the problem as a finite state machine with three states:

         buy
  REST --------→ HOLD
   ↑               |
   | cooldown       | sell
   |               ↓
  SOLD ←----------

State definitions:

HOLD: Maximum profit so far while holding a stock. Transitions from: held yesterday (HOLD → HOLD) or bought today from rest state (REST → HOLD).
SOLD: Maximum profit after selling today. Transitions from: sold today (HOLD → SOLD). Must cooldown next day.
REST: Maximum profit while free (no stock, no cooldown). Transitions from: was free yesterday (REST → REST) or cooldown expired (SOLD → REST).

Transition equations:

hold[i] = max(hold[i-1], rest[i-1] - prices[i])
sold[i] = hold[i-1] + prices[i]
rest[i] = max(rest[i-1], sold[i-1])

Since each day only depends on the previous day, we only need 3 variables — no array or table needed! This gives O(n) time and O(1) space.

The answer is max(sold[n-1], rest[n-1]) — at the end, we're either just sold or resting (holding a stock at the end is never optimal since we haven't realized the profit).

Step-by-Step Explanation

Let's trace with prices = [1, 2, 3, 0, 2]:

Step 1 (Day 0 — Base cases):

hold = -1 (bought at price 1)
sold = -∞ (can't sell without holding)
rest = 0 (doing nothing, profit = 0)

Step 2 (Day 1 — Price = 2):

hold = max(-1, 0-2) = max(-1, -2) = -1 (keep holding from day 0)
sold = -1 + 2 = 1 (sell! profit = 2 - 1 = 1)
rest = max(0, -∞) = 0 (still resting)

Step 3 (Day 2 — Price = 3):

hold = max(-1, 0-3) = -1 (still holding, buying at 3 is worse)
sold = -1 + 3 = 2 (sell at 3 would give profit 2)
rest = max(0, 1) = 1 ← sold[1]=1 transitions to rest after cooldown!

Step 4 (Day 3 — Price = 0):

hold = max(-1, 1-0) = 1 ← KEY MOMENT! rest=1 means we have profit 1 banked. Buying at price 0 costs nothing. hold = 1!
sold = -1 + 0 = -1 (selling at 0 is terrible)
rest = max(1, 2) = 2 ← sold[2]=2 becomes available after cooldown

Step 5 (Day 4 — Price = 2):

hold = max(1, 2-2) = 1 (keep holding)
sold = 1 + 2 = 3 ← RESULT! Sell at price 2 with hold=1 → profit 3!
rest = max(2, -1) = 2

Step 6: Answer = max(sold, rest) = max(3, 2) = 3.

The optimal strategy emerged naturally from the state transitions: Buy at 1 → Sell at 2 (profit 1) → Cooldown → Buy at 0 → Sell at 2 (profit 2) → Total = 3.

State Machine DP — Three States Evolving Day by Day — Watch the hold/sold/rest states update each day. Each cell depends only on the previous column — enabling O(1) space optimization with just 3 variables.

Algorithm

Initialize three state variables:
- hold = -prices[0] (bought on day 0)
- sold = -∞ (impossible to sell on day 0)
- rest = 0 (doing nothing)
For each day i from 1 to n-1:
- Save previous values: prevHold, prevSold, prevRest
- hold = max(prevHold, prevRest - prices[i]) — keep holding or buy today
- sold = prevHold + prices[i] — sell today
- rest = max(prevRest, prevSold) — stay resting or cooldown expired
Return max(sold, rest)

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;

        int hold = -prices[0];     // Bought stock on day 0
        int sold = INT_MIN;        // Can't sell without holding
        int rest = 0;              // Doing nothing

        for (int i = 1; i < (int)prices.size(); i++) {
            int prevHold = hold;
            int prevSold = sold;
            int prevRest = rest;

            hold = max(prevHold, prevRest - prices[i]);
            sold = prevHold + prices[i];
            rest = max(prevRest, prevSold);
        }
        return max(sold, rest);
    }
};

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0

        hold = -prices[0]           # Bought stock on day 0
        sold = float('-inf')        # Can't sell without holding
        rest = 0                    # Doing nothing

        for i in range(1, len(prices)):
            prev_hold = hold
            prev_sold = sold
            prev_rest = rest

            hold = max(prev_hold, prev_rest - prices[i])
            sold = prev_hold + prices[i]
            rest = max(prev_rest, prev_sold)

        return max(sold, rest)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;

        int hold = -prices[0];          // Bought stock on day 0
        int sold = Integer.MIN_VALUE;   // Can't sell without holding
        int rest = 0;                   // Doing nothing

        for (int i = 1; i < prices.length; i++) {
            int prevHold = hold;
            int prevSold = sold;
            int prevRest = rest;

            hold = Math.max(prevHold, prevRest - prices[i]);
            sold = prevHold + prices[i];
            rest = Math.max(prevRest, prevSold);
        }
        return Math.max(sold, rest);
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the prices array once, doing O(1) work per day (a few comparisons and additions). Total: O(n).

Space Complexity: O(1)

We use only 6 variables: hold, sold, rest, and their previous copies. No arrays, no tables, no recursion stack. Truly constant space.

Comparison of all three approaches:

Approach	Time	Space	Key Idea
Brute Force (Recursion)	O(2^n)	O(n)	Try all decisions
Memoization (Top-Down)	O(n)	O(n)	Cache subproblem results
State Machine DP	O(n)	O(1)	3 rolling variables

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Best Time to Buy and Sell Stock with Cooldown

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force - Recursion (Explore All Decisions)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Memoization (Top-Down DP)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - State Machine DP (Space Optimized)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis