DSAPrep
Medium2-D DP

Best Time to Buy And Sell Stock With Cooldown

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (buy one and sell one share of the stock multiple times) with the following restriction: after you sell your stock, you cannot buy stock on the next day (cooldown one day).

Note: you may not engage in multiple transactions simultaneously (you must sell the stock before you buy again).

Example 1

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2

Input: prices = [1]
Output: 0

Constraints

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000
View original on LeetCode ↗

On any given day you are in exactly one of three states: holding a share, just sold a share today (so tomorrow is a forced cooldown), or resting (not holding, free to buy). Each day’s best profit for a state only depends on yesterday’s states, which is what makes this a DP problem even though there is no explicit 2-D grid in the final solution — the “two dimensions” are day and state.

Brute Force Recursion

Time O(2^n)Space O(n)

At every day, if you are not holding a stock you can either buy or do nothing; if you are holding, you can either sell (which forces a cooldown the next day) or do nothing. Try every branch and take the best.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        def rec(i: int, holding: bool) -> int:
            if i >= n:
                return 0
            skip = rec(i + 1, holding)
            if holding:
                sell = prices[i] + rec(i + 2, False)
                return max(skip, sell)
            buy = -prices[i] + rec(i + 1, True)
            return max(skip, buy)
        return rec(0, False)

Two choices per day, and the same (day, holding) pair recurs constantly across different decision paths — exponential blow-up.

State Machine DP (Bottom-Up)

OptimalTime O(n)Space O(1)

Track the best possible profit for each of the three states after processing day i:

  • hold: currently holding a share.
  • sold: sold a share today (tomorrow must be a cooldown).
  • rest: not holding, and free to buy today.

Transitions, using yesterday’s values:

  • hold = max(hold, rest - prices[i]) — keep holding, or buy today from a resting state.
  • sold = hold + prices[i] — sell the share you were holding.
  • rest = max(rest, sold) — keep resting, or a cooldown day has passed since the last sale.
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0
        hold, sold, rest = -prices[0], 0, 0
        for price in prices[1:]:
            prev_hold, prev_sold, prev_rest = hold, sold, rest
            hold = max(prev_hold, prev_rest - price)
            sold = prev_hold + price
            rest = max(prev_rest, prev_sold)
        return max(sold, rest)

Tracing prices = [1, 2, 3, 0, 2] (columns are the three states):

hold
sold
rest
-1
0
0
day = 0price = 1
1 / 5
resultcurrent

Day 0: buying immediately gives hold = -1. sold and rest start at 0 (no profit yet, no stock sold).

Complexity: one pass over n days with O(1) work per day → O(n) time. Only three running values are kept → O(1) space.