MEDIUM

Best Time to Buy and Sell Stock with Cooldown

Given daily stock prices, maximize profit from any number of buy/sell transactions (never holding more than one share at a time), with the rule that after selling you must wait one full day before buying again.

Example

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

Output 3

Key Pointers

Track three running states per day instead of a full grid: currently holding a share, just sold today (triggers cooldown tomorrow), or resting (not holding, free to buy).
The cooldown rule only affects the "resting" state — it can only refresh from yesterday's "just sold" state, one day delayed.
Because each state only depends on the previous day's states, the whole problem collapses to O(1) space.

Step-by-Step Analysis

Initialize hold = -infinity (haven't bought yet), sold = 0, rest = 0.
For each day's price: remember yesterday's sold value first.
Update sold to hold + price (sell what you're holding today).
Update hold to max(hold, rest - price) (keep holding, or buy today from a resting state).
Update rest to max(rest, yesterday's sold) — cooldown means resting can only refresh from a sale that happened before today.
After the last day, the answer is max(sold, rest) — ending while still holding is never optimal.

Complexity

Time: O(n) — Space: O(1)

Code

def maxProfit(prices: list[int]) -> int:
    hold, sold, rest = float("-inf"), 0, 0

    for price in prices:
        prev_sold = sold
        sold = hold + price
        hold = max(hold, rest - price)
        rest = max(rest, prev_sold)

    return max(sold, rest)

Code Explanation

How the solution above works, piece by piece.

Track the best profit in three states: hold (own a share), sold (just sold today), rest (no share, allowed to buy).
sold = hold + price: selling today requires holding yesterday.
hold = max(hold, rest - price): keep holding, or buy today, but only from rest. Buying from yesterday's sold is not allowed, which is the cooldown rule.
rest = max(rest, prev_sold): stay resting, or come out of yesterday's cooldown. prev_sold keeps yesterday's value because sold was already overwritten.
The answer is max(sold, rest) (ending while holding is never best). O(n) time, O(1) space.

Visual Walkthrough

Running it on prices = [1, 2, 3, 0, 2]:

Each day has three possible states. sold can only come from hold, and buying can only happen from rest, never straight after a sale: that's the cooldown. On the last day the best is max(sold = 3, rest = 2) = 3.

answerresting after cooldown

Video Explanation

NeetCode — Best Time to Buy and Sell Stock with Cooldown, LeetCode 309