113.Best Time to Buy and Sell Stock with Cooldown

Medium2-D Dynamic Programming · 3/11

Problem

You are given an array prices where prices[i] is the price of a stock on day i. You may complete as many transactions as you like (buy one share, then sell it), with two restrictions:

You may hold at most one share at a time — you must sell before you buy again.
After you sell, you must wait one day (cooldown) before buying again.

Return the maximum profit you can achieve.

Examples

Input:  prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: buy day0 @1, sell day1 @2 (+1), cooldown day2, buy day3 @0, sell day4 @2 (+2).
             Selling @3 on day2 would also give +2, but then day3 is a cooldown and the
             cheap buy @0 is lost, so the total would only be 2.

Input:  prices = [1]
Output: 0
Explanation: A single day allows no transaction.

Input:  prices = [6, 1, 3, 2, 4, 7]
Output: 6
Explanation: buy @1 and sell @7 (+6). Splitting it (buy @1, sell @3, cooldown, buy @4, sell @7)
             only earns 2 + 3 = 5.

Constraints

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

💡 Key Insight

On each day you are in one of a few states — "free to buy" or "holding a share" — and the choice you make depends only on the day and the state, not on the history. That gives a DP over (day, state). The cooldown just means a sell on day i jumps to day i + 2 in the free state. Since each day only looks one or two days ahead, the whole table collapses to three running variables: hold, sold, rest.

Recursion (Brute Force)

TimeO(2^n)SpaceO(n)

Intuition

Let dfs(i, canBuy) be the best profit obtainable from day i onward.

If canBuy: either buy today (-prices[i] + dfs(i + 1, false)) or skip (dfs(i + 1, true)).
If holding: either sell today (+prices[i] + dfs(i + 2, true) — the +2 is the cooldown) or skip (dfs(i + 1, false)).

Base case: i >= n returns 0.

Algorithm

Define dfs(i, canBuy) as above with the two choices per state.
Return dfs(0, true).

Visualization

flowchart TD
    A["dfs(0, buy)<br/>price 1"] -->|"buy -1"| B["dfs(1, sell)<br/>price 2"]
    A -->|"skip"| C["dfs(1, buy)"]
    B -->|"sell +2"| D["dfs(3, buy)<br/>day 2 is cooldown"]
    B -->|"skip"| E["dfs(2, sell)<br/>price 3"]
    E -->|"sell +3"| F["dfs(4, buy) = 0"]
    D -->|"buy -0"| G["dfs(4, sell)"]
    G -->|"sell +2"| H["dfs(6) = 0"]
    H --> I["path: -1 +2 -0 +2 = 3"]

Code

java

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

    private int dfs(int[] prices, int i, boolean canBuy) {
        if (i >= prices.length) {
            return 0;
        }
        int skip = dfs(prices, i + 1, canBuy); // do nothing today
        if (canBuy) {
            int buy = dfs(prices, i + 1, false) - prices[i];
            return Math.max(buy, skip);
        }
        int sell = dfs(prices, i + 2, true) + prices[i]; // i+1 is the cooldown day
        return Math.max(sell, skip);
    }
}

Complexity

Time: O(2^n) — two choices per day.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

There are only 2n states (i, canBuy). Cache them.

Algorithm

memo[n][2] with a "not computed" marker (Integer null).
Same recursion, check the cache first, store the result before returning.

Dry Run

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

state      i=4  i=3  i=2  i=1  i=0
canBuy      0    2    2    2    3
holding     2    2    3    4    4

answer = memo[0][canBuy] = 3

Code

java

class Solution {
    private Integer[][] memo;
    private int[] prices;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        memo = new Integer[prices.length][2];
        return dfs(0, 1);
    }

    // state 1 = free to buy, 0 = holding a share
    private int dfs(int i, int canBuy) {
        if (i >= prices.length) {
            return 0;
        }
        if (memo[i][canBuy] != null) {
            return memo[i][canBuy];
        }
        int skip = dfs(i + 1, canBuy);
        int best;
        if (canBuy == 1) {
            best = Math.max(skip, dfs(i + 1, 0) - prices[i]);
        } else {
            best = Math.max(skip, dfs(i + 2, 1) + prices[i]); // cooldown
        }
        memo[i][canBuy] = best;
        return best;
    }
}

Complexity

Time: O(n) — 2n states, O(1) each.
Space: O(n) — memo plus recursion stack.

Bottom-Up 2-D Tabulation

TimeO(n)SpaceO(n)

Intuition

Fill the same table from the last day backward. Allocate n + 2 rows so dp[i + 2] is always valid (rows n and n + 1 are 0).

Recurrence:

dp[i][1] = max(dp[i+1][1], dp[i+1][0] - prices[i]) (free: skip or buy)
dp[i][0] = max(dp[i+1][0], dp[i+2][1] + prices[i]) (holding: skip or sell + cooldown)

Algorithm

dp = new int[n + 2][2].
For i from n - 1 down to 0, apply the recurrence.
Return dp[0][1].

Dry Run

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

i	price	dp[i][1] (free)	dp[i][0] (holding)
6	–	0	0
5	–	0	0
4	2	max(0, 0-2) = 0	max(0, 0+2) = 2
3	0	max(0, 2-0) = 2	max(2, 0+0) = 2
2	3	max(2, 2-3) = 2	max(2, 0+3) = 3
1	2	max(2, 3-2) = 2	max(3, 2+2) = 4
0	1	max(2, 4-1) = 3	max(4, 2+1) = 4

Code

java

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 2][2]; // extra rows absorb i+1 and i+2
        for (int i = n - 1; i >= 0; i--) {
            dp[i][1] = Math.max(dp[i + 1][1], dp[i + 1][0] - prices[i]); // skip / buy
            dp[i][0] = Math.max(dp[i + 1][0], dp[i + 2][1] + prices[i]); // skip / sell
        }
        return dp[0][1];
    }
}

Complexity

Time: O(n) — one pass.
Space: O(n) — the table.

State Machine with O(1) SpaceOptimal

TimeO(n)SpaceO(1)

Intuition

Walk forward through the days tracking the best profit at the end of today in each of three states:

hold — I own a share.
sold — I sold today (so tomorrow is a cooldown).
rest — I own nothing and am free to buy tomorrow.

Transitions:

hold' = max(hold, rest - price) — keep holding, or buy today (only allowed from rest, which enforces the cooldown).
sold' = hold + price — sell the share I held.
rest' = max(rest, sold) — stay idle, or yesterday's sale finished its cooldown.

The answer is max(sold, rest) after the last day.

Algorithm

hold = -infinity, sold = 0, rest = 0.
For each price: compute the three new values from the old values, then assign.
Return max(sold, rest).

Dry Run

flowchart LR
    R["rest"] -->|"buy: -price"| H["hold"]
    H -->|"keep"| H
    H -->|"sell: +price"| S["sold"]
    S -->|"cooldown"| R
    R -->|"idle"| R

prices = [1, 2, 3, 0, 2]
day  price   hold   sold   rest
0    1        -1    -inf    0
1    2        -1     1      0
2    3        -1     2      1
3    0         1    -1      2
4    2         1     3      2     → max(sold, rest) = 3

Code

java

class Solution {
    public int maxProfit(int[] prices) {
        int hold = Integer.MIN_VALUE / 2; // impossible to hold before day 0
        int sold = Integer.MIN_VALUE / 2; // nothing sold yet
        int rest = 0;
        for (int price : prices) {
            int prevSold = sold;
            sold = hold + price;                 // sell today
            hold = Math.max(hold, rest - price); // keep or buy (only from rest)
            rest = Math.max(rest, prevSold);     // idle or finish cooldown
        }
        return Math.max(sold, rest);
    }
}

Complexity

Time: O(n) — constant work per day.
Space: O(1) — three variables.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2^n)	O(n)
Top-Down Memoization	O(n)	O(n)
Bottom-Up 2-D Tabulation	O(n)	O(n)
State Machine	O(n)	O(1)

Common Pitfalls

Selling to i + 1 instead of i + 2 in the recursion — that ignores the cooldown and solves the unrestricted problem.
Updating hold, sold, rest in place without saving old values — rest must use yesterday's sold.
Allowing a buy from sold instead of rest — that skips the cooldown.
Initializing hold = 0 — you cannot be holding a share for free; use a very negative value (not Integer.MIN_VALUE itself, which overflows when you add a price).
Using an array of size n + 1 for tabulation — the sell transition reads dp[i + 2], so you need n + 2.