Best Time To Buy And Sell Stock With Cooldown

The Best Time to Buy and Sell Stock with Cooldown problem is a classic dynamic programming challenge that tests a developer's ability to manage state transitions under specific constraints. Unlike the simpler versions where you can trade freely, this variation introduces a mandatory rest period after selling, fundamentally altering the strategy for maximizing profit. Understanding the mechanics behind this algorithm is essential for coding interviews and for building a solid foundation in state machine logic.

Understanding the Problem Constraints

Before diving into the solution, it is critical to define the rules clearly. You are given an array prices where prices[i] represents the price of a stock on the i-th day. The goal is to maximize profit by completing as many transactions as you like, but with three specific restrictions:

1. Single Holding: You may not engage in multiple transactions simultaneously. You must sell the stock before you buy again.
2. Cooldown Period: After you sell a stock, you cannot buy on the very next day. There is a mandatory one-day cooldown.
3. No Shorting: You cannot sell a stock you do not own.

These constraints transform the problem from a simple greedy accumulation of positive slopes into a state management exercise. On any given day, your action depends entirely on what you did the previous day.

Defining the States: The Foundation of the Solution

The most solid way to solve this is by modeling the problem as a Finite State Machine (FSM). And at the end of each day, you exist in exactly one of three states. Defining these states precisely is the key to writing clean, bug-free code.

State 1: Holding a Stock (hold)

You currently own a share of stock. You either bought it today or were holding it from a previous day.

• Transition: You can stay in this state (do nothing) or transition to Sold by selling today.
• Profit Value: Represents the maximum profit achievable ending day i while holding a stock. Since buying costs money, this value is typically negative or low initially.

State 2: Not Holding, In Cooldown (sold / cooldown)

You sold a stock today. Because you just sold, you are forced into a cooldown for tomorrow.

• Transition: You can only arrive here from the hold state by selling today. You cannot stay in this state for more than one day.
• Profit Value: Maximum profit ending day i having just sold the stock.

State 3: Not Holding, Free to Buy (rest / free)

You do not own a stock, and you are not in a cooldown. You are free to buy tomorrow (or today, technically, but buying today moves you to hold).

• Transition: You arrive here either by staying in rest (doing nothing yesterday and today) or by moving from sold (yesterday was a cooldown day, today you are free).
• Profit Value: Maximum profit ending day i with no stock and no restrictions.

Deriving the Recurrence Relations

With the states defined, we can write the mathematical recurrence relations that describe how the maximum profit evolves day by day. Let n be the number of days (length of prices array). We define three arrays (or variables for space optimization): hold[i], sold[i], rest[i] Small thing, real impact. Turns out it matters..

1. Transition to hold[i]

To be holding a stock at the end of day i, two scenarios are possible:

• Scenario A: You were already holding yesterday (hold[i-1]) and did nothing today.
• Scenario B: You were free yesterday (rest[i-1]) and bought the stock today. This costs prices[i].

Formula: hold[i] = max(hold[i-1], rest[i-1] - prices[i])

2. Transition to sold[i]

To be in the "just sold" state at the end of day i, there is only one way:

• You must have been holding a stock yesterday (hold[i-1]) and you sell it today for prices[i].

Formula: sold[i] = hold[i-1] + prices[i]

3. Transition to rest[i]

To be free and resting at the end of day i, two scenarios exist:

• Scenario A: You were resting yesterday (rest[i-1]) and did nothing today.
• Scenario B: You were in sold (cooldown) yesterday (sold[i-1]). The cooldown has passed, so today you are free.

Formula: rest[i] = max(rest[i-1], sold[i-1])

Base Cases and Initialization

Correct initialization prevents off-by-one errors. Consider Day 0 (index 0):

• hold[0] = -prices[0]: If we buy on day 0, our profit is negative the price.
• sold[0] = -Infinity (or a very small number): It is impossible to sell on day 0 because we cannot own a stock before the market opens.
• rest[0] = 0: We start with zero profit, no stock, and no cooldown.

The Final Answer

The maximum profit at the end of the last day (n-1) cannot be in the hold state, because holding an unsold stock represents unrealized profit (an asset, not cash). The final answer is the maximum of the two "not holding" states:

Result = max(sold[n-1], rest[n-1])

Space Optimization: O(1) Space Complexity

Notice that the calculation for day i depends only on the values from day i-1. That said, we do not need to store the entire history arrays. We can use simple variables to track the previous state, reducing space complexity from O(N) to O(1).

Here is the optimized logic flow in pseudocode:

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

FOR price IN prices[1:]:
    prev_hold = hold
    prev_sold = sold
    prev_rest = rest

    hold = max(prev_hold, prev_rest - price)
    sold = prev_hold + price
    rest = max(prev_rest, prev_sold)

RETURN max(sold, rest)

Step-by-Step Walkthrough with an Example

Let’s trace the algorithm with prices = [1, 2, 3, 0, 2] The details matter here. Worth knowing..

Initialization (Day 0, Price = 1):

• hold = -1 (Bought at 1)
• sold = -inf
• rest = 0

Day 1 (Price = 2):

• prev_hold = -1, prev_sold = -inf, prev_rest = 0
• hold = max(-1, 0 - 2) = -1 (Keep holding bought at 1)
• sold = -1 + 2 = 1 (Sell the stock bought at 1)
• rest = max(0, -inf) = 0

Day 2 (Price = 3):

• prev_hold = -1, prev_sold = 1, prev_rest = 0
• hold = max(-1, 0 - 3) = -1 (Still holding the cheap stock)
• sold = -1 + 3 = 2 (Sell stock bought at 1 for 3 -> Profit 2)
• rest = max(0, 1) = 1 (Yesterday