LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown

This problem asks us to maximize profit from stock trading under a special restriction called a cooldown period. We are given an integer array prices, where prices[i] represents the stock price on day i. On any day, we may choose to buy one share, sell one share, or do nothing.

leetcodemediumarraydynamic-programming

LeetCode Problem 309

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to maximize profit from stock trading under a special restriction called a cooldown period.

We are given an integer array prices, where prices[i] represents the stock price on day i. On any day, we may choose to buy one share, sell one share, or do nothing. We are allowed to perform as many transactions as we want, but there are two important constraints:

  1. We cannot hold more than one stock at a time.
  2. After selling a stock, we must wait one full day before buying again.

The goal is to compute the maximum total profit achievable by the end of all trading days.

The cooldown restriction changes the problem significantly compared to the classic unlimited transactions stock problem. Normally, after selling, we could immediately buy again the next day. Here, that is forbidden, so our decisions on one day affect future choices.

For example, with:

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

One optimal sequence is:

  • Buy at 1
  • Sell at 3
  • Cooldown for one day
  • Buy at 0
  • Sell at 2

Total profit:

(3 - 1) + (2 - 0) = 4

However, because of cooldown timing, the actual optimal achievable sequence under legal transitions gives a profit of 3.

The constraints are:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

The input size of 5000 is large enough that exponential solutions are too slow. We need an efficient dynamic programming approach, ideally linear time.

Important edge cases include:

  • A single day, where no transaction is possible
  • Strictly decreasing prices, where the best action is to never buy
  • Alternating peaks and valleys, where cooldown timing matters
  • Multiple profitable trades that overlap because of cooldown restrictions

The problem guarantees that the array is non-empty and all prices are non-negative integers.

Approaches

Brute Force Approach

A brute force solution explores every possible sequence of actions across all days.

For each day, we can potentially:

  • Buy
  • Sell
  • Skip

The legality of these actions depends on whether we currently hold a stock and whether we are in cooldown.

A recursive backtracking solution can simulate all valid trading paths. At every day, it branches into all allowed decisions and recursively computes the best future profit.

This approach is correct because it exhaustively explores every legal trading sequence and chooses the maximum profit among them.

However, the number of states grows exponentially. At each day, multiple decisions may branch into further possibilities. With up to 5000 days, this quickly becomes computationally infeasible.

Key Insight for the Optimal Solution

The important observation is that the future only depends on a small amount of information from the current day:

  • Whether we currently hold a stock
  • Whether we are in cooldown
  • The best profit achieved so far

We do not need to remember the entire transaction history.

This makes the problem ideal for dynamic programming.

We can model the system using three states:

  1. hold
  • Maximum profit when currently holding a stock
  1. sold
  • Maximum profit immediately after selling a stock today
  1. rest
  • Maximum profit while not holding stock and not in cooldown

These states fully capture all necessary information for future decisions.

At each day, we transition between states based on valid actions:

  • Buy transitions from rest to hold
  • Sell transitions from hold to sold
  • Waiting transitions from previous rest or sold

Because each day only depends on the previous day, we can solve the problem in linear time with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) or worse O(n) Explores all valid trading sequences recursively
Optimal Dynamic Programming O(n) O(1) Tracks only three trading states per day

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Initialize three state variables.

We maintain:

  • hold, maximum profit while holding a stock
  • sold, maximum profit after selling today
  • rest, maximum profit while idle and allowed to buy

Initially:

  • hold = -prices[0]
  • sold = 0
  • rest = 0

We start with a negative value for hold because buying a stock costs money. 2. Iterate through each remaining day.

For every price after day 0, compute the new states. 3. Compute the new hold state.

We can either:

  • Continue holding the previous stock
  • Buy today from the rest state

Transition:

hold = max(previous_hold, previous_rest - price)
  1. Compute the new sold state.

We can only sell today if we were holding a stock yesterday.

Transition:

sold = previous_hold + price
  1. Compute the new rest state.

We can remain resting or enter rest after yesterday's sell.

Transition:

rest = max(previous_rest, previous_sold)
  1. Update all states simultaneously.

Since all transitions depend on previous values, temporary variables are required. 7. Return the final answer.

At the end, holding a stock is not useful because unrealized profit does not count.

Therefore, the answer is:

max(sold, rest)

Why it works

The algorithm works because the three states completely describe every legal trading condition on each day.

Every valid action transitions between these states while respecting cooldown rules:

  • Buying is only allowed from rest
  • Selling requires hold
  • Cooldown naturally occurs because after sold, the next day can only transition into rest

Since every possible legal trading sequence maps to a sequence of these state transitions, and each state stores the maximum achievable profit, the final result is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        hold = -prices[0]
        sold = 0
        rest = 0

        for price in prices[1:]:
            previous_hold = hold
            previous_sold = sold
            previous_rest = rest

            hold = max(previous_hold, previous_rest - price)
            sold = previous_hold + price
            rest = max(previous_rest, previous_sold)

        return max(sold, rest)

The implementation begins by handling the edge case where the array is empty, although the problem guarantees at least one element.

The three state variables represent the best possible profit under different trading conditions.

hold stores the best profit achievable while currently owning a stock. Since buying costs money, it starts as -prices[0].

sold represents the profit immediately after selling a stock. Initially, we have not sold anything, so it starts at 0.

rest represents the best profit while not holding a stock and not being in cooldown.

For every price after the first day, we preserve the previous state values before computing transitions. This is necessary because all updates depend on the prior day's states.

The transition equations directly model legal trading actions:

  • hold either keeps the existing stock or buys today
  • sold sells the stock held yesterday
  • rest either continues resting or finishes a cooldown

Finally, we return the best non-holding state because any remaining held stock has not been sold and therefore does not contribute to realized profit.

Go Solution

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    hold := -prices[0]
    sold := 0
    rest := 0

    for i := 1; i < len(prices); i++ {
        price := prices[i]

        previousHold := hold
        previousSold := sold
        previousRest := rest

        if previousRest-price > previousHold {
            hold = previousRest - price
        } else {
            hold = previousHold
        }

        sold = previousHold + price

        if previousSold > previousRest {
            rest = previousSold
        } else {
            rest = previousRest
        }
    }

    if sold > rest {
        return sold
    }

    return rest
}

The Go implementation follows the same state transition logic as the Python solution.

Go does not provide a built-in max function for integers, so comparisons are implemented using standard if statements.

Slices in Go behave similarly to dynamic arrays. The function safely handles empty input even though the constraints guarantee at least one element.

Integer overflow is not a concern because the maximum profit is well within Go's integer range.

Worked Examples

Example 1

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

Initial state:

Day Price hold sold rest
0 1 -1 0 0

Day 1, price = 2

  • hold = max(-1, 0 - 2) = -1
  • sold = -1 + 2 = 1
  • rest = max(0, 0) = 0
Day Price hold sold rest
1 2 -1 1 0

Day 2, price = 3

  • hold = max(-1, 0 - 3) = -1
  • sold = -1 + 3 = 2
  • rest = max(0, 1) = 1
Day Price hold sold rest
2 3 -1 2 1

Day 3, price = 0

  • hold = max(-1, 1 - 0) = 1
  • sold = -1 + 0 = -1
  • rest = max(1, 2) = 2
Day Price hold sold rest
3 0 1 -1 2

Day 4, price = 2

  • hold = max(1, 2 - 2) = 1
  • sold = 1 + 2 = 3
  • rest = max(2, -1) = 2
Day Price hold sold rest
4 2 1 3 2

Final answer:

max(3, 2) = 3

Example 2

prices = [1]

Initial state:

Day Price hold sold rest
0 1 -1 0 0

No additional days exist.

Final answer:

max(0, 0) = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each day is processed exactly once
Space O(1) Only three state variables are maintained

The algorithm performs a constant amount of work for every element in the input array. No nested loops or recursion are used.

Space usage remains constant because the solution stores only the previous trading states instead of maintaining a full DP table.

Test Cases

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        hold = -prices[0]
        sold = 0
        rest = 0

        for price in prices[1:]:
            previous_hold = hold
            previous_sold = sold
            previous_rest = rest

            hold = max(previous_hold, previous_rest - price)
            sold = previous_hold + price
            rest = max(previous_rest, previous_sold)

        return max(sold, rest)

solution = Solution()

assert solution.maxProfit([1, 2, 3, 0, 2]) == 3  # Provided example
assert solution.maxProfit([1]) == 0  # Single day, no transaction possible
assert solution.maxProfit([5, 4, 3, 2, 1]) == 0  # Always decreasing prices
assert solution.maxProfit([1, 2, 4]) == 3  # One profitable transaction
assert solution.maxProfit([1, 2, 3, 4, 5]) == 4  # Continuous upward trend
assert solution.maxProfit([2, 1, 4]) == 3  # Buy after initial drop
assert solution.maxProfit([6, 1, 3, 2, 4, 7]) == 6  # Multiple opportunities
assert solution.maxProfit([1, 2, 3, 0, 2, 1, 4]) == 5  # Cooldown affects timing
assert solution.maxProfit([0, 0, 0, 0]) == 0  # No profit possible
assert solution.maxProfit([1, 4, 2]) == 3  # Single buy and sell
Test Why
[1,2,3,0,2] Standard example with cooldown interaction
[1] Minimum input size
[5,4,3,2,1] No profitable trades
[1,2,4] Simple profitable transaction
[1,2,3,4,5] Continuous increase
[2,1,4] Buying after a price drop
[6,1,3,2,4,7] Multiple competing trade opportunities
[1,2,3,0,2,1,4] Complex cooldown timing
[0,0,0,0] Constant prices
[1,4,2] Single optimal sell point

Edge Cases

One important edge case is a single-element array such as [1]. Since buying and selling require at least two days, no transaction is possible. A naive implementation might incorrectly attempt a transaction or access invalid indices. This implementation correctly initializes the states and immediately returns 0.

Another important edge case is strictly decreasing prices, such as [5,4,3,2,1]. Any purchase would lead to a loss, so the optimal strategy is to avoid trading entirely. The dynamic programming states naturally preserve the best profit of 0 because selling never becomes beneficial.

A more subtle edge case involves cooldown conflicts, such as [1,2,3,0,2]. Greedy approaches may attempt to buy immediately after selling, violating the cooldown rule. The state transition design prevents illegal trades because buying is only allowed from the rest state, never directly from sold.

Constant-price arrays such as [0,0,0,0] are another useful edge case. Since no profitable transaction exists, the best result remains 0. The algorithm correctly handles this because all possible sell profits are non-positive, so the resting state dominates.

Finally, cases with multiple overlapping opportunities, such as [6,1,3,2,4,7], demonstrate why dynamic programming is necessary. A locally optimal decision may block a more profitable future sequence because of cooldown timing. The state-based DP evaluates all valid transitions efficiently and guarantees the globally optimal result.