AlgoMaster Logo

Best Time to Buy and Sell Stock with Cooldown

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

You can make as many transactions as you like, but after every sell you must wait one day before buying again. Without that cooldown, the greedy strategy of taking every price increase would be optimal. The cooldown breaks it: selling on day i locks you out of buying on day i+1, so a sell today can cost you a better opportunity tomorrow. At each point you have to weigh selling now and sitting out a day against holding and selling later.

That decision structure is a state machine. On any given day you are in one of a few states, and each state allows different moves. The cooldown adds a third state beyond the usual "holding" and "not holding".

Key Constraints:

  • 1 <= prices.length <= 5000 → O(n^2) is about 25 million operations, which would pass but is unnecessary. Every approach below runs in O(n).
  • 0 <= prices[i] <= 1000 → Total profit is at most 5000 × 1000, so a 32-bit integer is enough. Prices can be zero, so buying at no cost is possible.

Approach 1: Recursion with Memoization

Intuition

On each day the decision depends on a single piece of state: whether you currently hold a stock. If you hold one, you can sell or keep holding. If you do not, you can buy or skip the day. Define a recursive function dfs(day, holding) that returns the maximum profit from day day onwards. A sell jumps to day + 2 instead of day + 1, which enforces the cooldown without tracking it as separate state.

The recursion has overlapping subproblems. dfs(3, false) can be reached from multiple paths: by selling on day 1 (cooldown on day 2, resume on day 3) or by skipping days 1 and 2. Memoization computes each (day, holding) pair once.

Algorithm

  1. Define dfs(day, holding) as the max profit from day onwards.
  2. Base case: if day >= n, return 0.
  3. If holding: either sell today (profit = prices[day] + dfs(day + 2, false), because selling triggers cooldown) or hold (dfs(day + 1, true)).
  4. If not holding: either buy today (-prices[day] + dfs(day + 1, true)) or skip (dfs(day + 1, false)).
  5. Memoize on (day, holding).
  6. Return dfs(0, false).

Example Walkthrough

0
1
1
2
2
3
3
0
4
2
prices

The call dfs(0, false) branches into buy and skip, and memoization fills the table from the last day backwards. Writing holding = 0 for "not holding" and holding = 1 for "holding", and using dfs(day, ·) = 0 for day >= 5, the cached values are:

Scroll

State

Choices

Value

dfs(4, 1)

sell: 2 + dfs(6, 0) = 2, hold: dfs(5, 1) = 0

2

dfs(4, 0)

buy: -2 + dfs(5, 1) = -2, skip: dfs(5, 0) = 0

0

dfs(3, 1)

sell: 0 + dfs(5, 0) = 0, hold: dfs(4, 1) = 2

2

dfs(3, 0)

buy: -0 + dfs(4, 1) = 2, skip: dfs(4, 0) = 0

2

dfs(2, 1)

sell: 3 + dfs(4, 0) = 3, hold: dfs(3, 1) = 2

3

dfs(2, 0)

buy: -3 + dfs(3, 1) = -1, skip: dfs(3, 0) = 2

2

dfs(1, 1)

sell: 2 + dfs(3, 0) = 4, hold: dfs(2, 1) = 3

4

dfs(1, 0)

buy: -2 + dfs(2, 1) = 1, skip: dfs(2, 0) = 2

2

dfs(0, 0)

buy: -1 + dfs(1, 1) = 3, skip: dfs(1, 0) = 2

3

The function returns dfs(0, 0) = 3. The winning path reads off the choices: buy at day 0 (price 1), sell at day 1 (price 2), cooldown on day 2, buy at day 3 (price 0), sell at day 4 (price 2), for a profit of 1 + 2 = 3.

Code

The recursion carries call-stack and memo-lookup overhead. The next approach computes the same answer iteratively, tracking the best profit up to each day instead of from each day onwards, and makes the state machine explicit.

Approach 2: Bottom-Up DP with State Machine

Intuition

Model each day as one of three states:

  1. Held - You're holding a stock (either you bought today or you've been holding from before).
  2. Sold - You sold your stock today. Tomorrow you must cool down.
  3. Rest - You don't hold a stock and you're not in cooldown. You're free to buy.

The transitions are: from Rest, buy (to Held) or do nothing (stay Rest). From Held, sell (to Sold) or do nothing (stay Held). From Sold, you must cool down (to Rest). Each transition becomes one recurrence, computed for every day.

Algorithm

  1. Initialize three arrays: held[0] = -prices[0], sold[0] = 0, rest[0] = 0.
  2. For each day from 1 to n-1:
    • held[i] = max(held[i-1], rest[i-1] - prices[i])
    • sold[i] = held[i-1] + prices[i]
    • rest[i] = max(rest[i-1], sold[i-1])
  3. Return max(sold[n-1], rest[n-1]).

Example Walkthrough

1Day 0: price=1. held=-1 (buy), sold=0, rest=0
0
1
day 0
1
2
2
3
3
0
4
2
1/6
held
1held[0] = -1 (bought stock at price 1)
0
-1
1
0
2
0
3
0
4
0
sold
1sold[0] = 0 (can't sell without holding)
0
0
1
0
2
0
3
0
4
0
rest
1rest[0] = 0 (no profit yet, free to buy)
0
0
1
0
2
0
3
0
4
0
1/6

Code

Each recurrence reads only the previous day's values, so the three arrays are unnecessary. The next approach replaces them with three variables.

Approach 3: Space-Optimized State Machine DP

Intuition

When a DP recurrence has a look-back window of one day, the arrays collapse to scalar variables: keep one value per state and overwrite it each iteration.

The one detail that matters is update order. Running the three updates in sequence would feed already-overwritten values into later updates: sold needs the old held, and rest needs the old sold. Saving all three old values in temporaries before updating any of them makes the order irrelevant.

Algorithm

  1. Initialize held = -prices[0], sold = 0, rest = 0.
  2. For each day from 1 to n-1:
    • Save old values: prevHeld = held, prevSold = sold, prevRest = rest.
    • held = max(prevHeld, prevRest - prices[i])
    • sold = prevHeld + prices[i]
    • rest = max(prevRest, prevSold)
  3. Return max(sold, rest).

Example Walkthrough

prices
1Init: held=-1 (buy at 1), sold=0, rest=0
0
1
day 0
1
2
2
3
3
0
4
2
state variables
1Day 0: held=-1 (bought), sold=0, rest=0
held
:
-1
sold
:
0
rest
:
0
1/6

Code

The three-state machine is not the only O(1)-space formulation. The cooldown can also be encoded with the usual two states plus a look-back of two days.

Approach 4: Two-State DP with a Two-Day Look-Back

Intuition

Keep the two states from the unrestricted trading problem: hold[i], the best profit after day i while holding a stock, and free[i], the best profit after day i while not holding one. The cooldown only affects buying: if you buy on day i, your most recent sell happened on day i-2 at the latest. So the buy transition reads the not-holding profit from two days back:

  • hold[i] = max(hold[i-1], free[i-2] - prices[i])
  • free[i] = max(free[i-1], hold[i-1] + prices[i])

Reading only free[i-2] is safe even though sells from day i-3 and earlier also qualify: free is non-decreasing (each free[i] takes a max with free[i-1]), so free[i-2] already includes the best of every earlier day.

This collapses Approach 2's Sold and Rest into a single free state. Three scalars are enough: hold, free, and prevFree, the value of free two days back.

Algorithm

  1. Initialize hold = -prices[0], free = 0, prevFree = 0 (the not-holding profit before day 0 is 0).
  2. For each day i from 1 to n-1:
    • newHold = max(hold, prevFree - prices[i])
    • newFree = max(free, hold + prices[i])
    • Shift: prevFree = free, then hold = newHold, free = newFree.
  3. Return free.

Example Walkthrough

prices
1Day 0: hold=-1 (buy at price 1), free=0, prevFree=0
0
1
day 0
1
2
2
3
3
0
4
2
state variables
1Day 0: buy at price 1
hold
:
-1
free
:
0
prevFree
:
0
1/6

Day 3 is where the look-back matters. The buy uses prevFree = 1, the profit available by day 1, rather than free = 2, which includes a sell on day 2 that would make a day 3 buy illegal.

Code