Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown

What is this problem about?

The "Best Time to Buy and Sell Stock with Cooldown interview question" introduces a realistic constraint to the stock trading problem. You can complete as many transactions as you like, but after you sell a stock, you cannot buy again on the next day. This one-day "cooldown" period forces you to carefully time your exits to maximize future entry opportunities.

Why is this asked in interviews?

Companies like Goldman Sachs, Microsoft, and Meta ask the "Best Time to Buy and Sell Stock with Cooldown coding problem" to test a candidate's ability to model complex state transitions. It’s a classic "Dynamic Programming" problem where the decision today (to sell or not) has a direct impact on the available actions two days from now. It evaluates "State Machine" design skills.

Algorithmic pattern used

This problem is solved using Dynamic Programming with State Transition. We define three states for each day $i$:

1. Hold: You currently own a stock. You either bought it today or were already holding it.
   • hold[i] = max(hold[i-1], reset[i-1] - prices[i])
2. Sold: You just sold a stock today. You are now entering the mandatory cooldown.
   • sold[i] = hold[i-1] + prices[i]
3. Reset: You don't own a stock and you are NOT in a cooldown. You are free to buy.
   • reset[i] = max(reset[i-1], sold[i-1]) The maximum profit on the last day will be the maximum of the sold and reset states.

Example explanation

Prices: [1, 2, 3, 0, 2]

• Day 1 (1): Buy. hold = -1.
• Day 2 (2): Sell. sold = 1. (Now in cooldown for Day 3).
• Day 3 (3): Must stay in reset because of cooldown. reset = 1.
• Day 4 (0): Buy. hold = 1 - 0 = 1.
• Day 5 (2): Sell. sold = 1 + 2 = 3. Max Profit: 3.

Common mistakes candidates make

• Ignoring the Cooldown: Trying to solve it as a regular Stock II problem, which leads to overestimating the profit.
• Incorrect State Mapping: Confusing the "Cooldown" state with the "Reset" state. You can only buy from the "Reset" state, and you only enter "Reset" the day after a "Sold" state.
• Complexity: Attempting a $O(N^2)$ DP when the three-state $O(N)$ approach is much more efficient.

Interview preparation tip

When a problem involves "waiting" or "cooldowns," think of it as a state machine. Draw the states (Hold, Sold, Reset) and the arrows between them. Once the diagram is clear, the "Dynamic Programming" equations almost write themselves.