AlgoMaster Logo

Best Time to Buy and Sell Stock with Cooldown

Last Updated: March 28, 2026

medium
4 min read

Understanding the Problem

This is a twist on the classic stock trading series. You can make unlimited transactions, but there's a catch: after every sell, you must wait one day before buying again. That cooldown changes the entire decision structure.

Without the cooldown, you could greedily grab every upward price movement. With it, selling on day i locks you out of buying on day i+1. So a sell today might cost you a better opportunity tomorrow. The question becomes: at each point, are you better off selling now and sitting out a day, or holding and selling later?

This naturally leads to a state machine. On any given day, you're in one of a few states, and each state has different transitions available. The cooldown introduces a third state beyond the usual "holding" and "not holding" that makes this problem more interesting than the basic stock variants.

Key Constraints:

  • 1 <= prices.length <= 5000 → With n up to 5000, O(n^2) is 25 million operations which is borderline. O(n) would be comfortable, and O(n log n) is fine too.
  • 0 <= prices[i] <= 1000 → Prices can be zero, which means buying for free is possible. Prices are bounded, so overflow isn't a concern.

Approach 1: Recursion with Memoization

Intuition

The most natural way to think about this problem is top-down. At each day, you make a choice based on your current state. If you're not holding stock and not in cooldown, you can buy or skip. If you're holding stock, you can sell or hold. If you just sold, you're forced to cool down.

Let's define a recursive function dfs(day, holding) that returns the maximum profit from day day onwards, where holding indicates whether we currently hold a stock. After a sell, we skip the next day (jumping to day + 2), which naturally enforces the cooldown.

The recursive structure gives us overlapping subproblems. For example, dfs(3, false) might be called from multiple paths: from selling on day 1 (cooldown day 2, then day 3) or from skipping days 1 and 2. Memoization eliminates the redundant computation.

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 recursion explores all paths. Starting from dfs(0, false):

  • Buy at day 0 (price 1), then sell at day 1 (price 2), cooldown day 2, buy at day 3 (price 0), sell at day 4 (price 2) = profit 3
  • Each (day, holding) pair is computed once and cached, giving us O(n) total work.

Code

The recursion with memoization works, but it carries overhead from the call stack and memo lookups. Since we process days sequentially, can we fill a table iteratively and avoid the stack entirely?

Approach 2: Bottom-Up DP with State Machine

Intuition

Let's think about this as a state machine. On any given day, you're in 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 just 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). This gives us three recurrences that we compute for each 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
1held[0] = -1 (bought stock at price 1)
0
-1
1
0
2
0
3
0
4
0
1/6
1sold[0] = 0 (can't sell without holding)
0
0
1
0
2
0
3
0
4
0
1/6
1rest[0] = 0 (no profit yet, free to buy)
0
0
1
0
2
0
3
0
4
0
1/6

Code

The time is already O(n), but we're storing three entire arrays when the recurrence only looks at the previous day. Can we just track three variables and overwrite them each day?

Approach 3: Space-Optimized State Machine DP

Intuition

Since each day's computation only uses the previous day's values, we can replace the three arrays with three variables. This is the same optimization we'd apply to Fibonacci or House Robber: when the DP recurrence has a window of size 1, collapse the array to variables.

The only subtlety is update order. We need to use the old values of all three states when computing the new values. The cleanest fix is to save all three old values in temporaries before updating any of them.

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

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

Code