Best Time to Buy and Sell Stock with Cooldown

medium2D Dynamic Programming34 stepsJava · Python · C++

Trade as often as you like, but after selling you must wait a day. Track three states each day: hold (own a share), sold (just sold today), rest (no share, free to buy). Each state's best value comes from yesterday's states.

▶ Watch the animated trace

Traced input: prices = [1, 2, 3, 0, 2] → 3. Original problem: neetcode.io/problems/buy-and-sell-crypto-with-cooldown

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Three variables per day.

Key idea

hold = max(hold, rest − price): keep holding, or buy today from a rested state.
sold = hold + price: sell what you held.
rest = max(rest, sold): yesterday's sale forces today's rest.
Answer: max(sold, rest); you never end holding.

Common mistakes

Buying from sold ignores the cooldown.
Updating states in place without saving yesterday's values.

Solution

Java

int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int i = 0; i < prices.length; i++) {
        int p = prices[i];
        int prevSold = sold;
        sold = hold == Integer.MIN_VALUE ? Integer.MIN_VALUE : hold + p;
        hold = Math.max(hold, rest - p);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

Python

def maxProfit(prices: List[int]) -> int:
    hold, sold, rest = float("-inf"), 0, 0
    for p in prices:
        prev_sold = sold
        sold = hold + p
        hold = max(hold, rest - p)
        rest = max(rest, prev_sold)
    return max(sold, rest)

C++

int maxProfit(vector<int>& prices) {
    int hold = INT_MIN, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = hold == INT_MIN ? INT_MIN : hold + p;
        hold = max(hold, rest - p);
        rest = max(rest, prevSold);
    }
    return max(sold, rest);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single day No time to sell.	`prices = [1]`	`0`
Falling prices Never buy.	`prices = [5, 4, 3]`	`0`
Cooldown matters Buying at 1 and selling at 7 earns 6. Doing 1→4 and then 2→7 would need buying the day right after selling.	`prices = [1, 4, 2, 7]`	`6`