LeetCode · #309

Stock with Cooldown Solution

Find the maximum profit from buying and selling stock with a 1-day cooldown after each sell.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #309

🏗️

Pattern

DP — state machine

Given an array of stock prices, find max profit with unlimited transactions. After selling, you must wait one day before buying again (cooldown).

Example

Input: prices = [1,2,3,0,2]
Output: 3 // Buy day 0, sell day 2 (profit 2), cooldown day 3, buy day 3, sell day 4 (profit 2). Total=3.

Constraints

• 1 ≤ prices.length ≤ 5000 • 0 ≤ prices[i] ≤ 1000

Section Two · Approach 1

Recursion — O(2ⁿ)

At each day, decide: buy, sell, or skip. Track state (holding or not) and cooldown. Recurse on all choices.

Why it works

Explores every possible sequence of buy/sell/hold decisions.

Why we can do better

Problem: Overlapping subproblems. State-machine DP tracks three states per day in O(n) time, O(1) space.

Java — Recursive with memoization

 class Solution {
public int maxProfit(int[] prices) {
return dfs(prices, 0, false, new HashMap<>());
    }
private int dfs(int[] p, int i, boolean hold, Map<String,Integer> memo) {
if (i >= p.length) return 0;
String key = i + "," + hold;
if (memo.containsKey(key)) return memo.get(key);
int skip = dfs(p, i+1, hold, memo);
int act = hold
            ? p[i] + dfs(p, i+2, false, memo) // sell + cooldown
: -p[i] + dfs(p, i+1, true, memo); // buy
memo.put(key, Math.max(skip, act));
return Math.max(skip, act);
    }
}

Python — Recursive with cache

 from functools import lru_cache
class Solution:
def maxProfit(self, prices: list[int]) -> int:
        @lru_cache(maxsize=None)
def dfs(i, hold):
if i >= len(prices): return 0
skip = dfs(i+1, hold)
if hold: act = prices[i] + dfs(i+2, False)
else: act = -prices[i] + dfs(i+1, True)
return max(skip, act)
return dfs(0, False)

Metric	Value
Time	O(n) with memo
Space	O(n)

Section Three · Approach 2

State Machine DP — O(n) time, O(1) space

Three states: hold (own stock), sold (just sold, in cooldown), rest (no stock, free to buy). Transition daily between states.

💡 Mental model: Imagine a traffic light with three states. Green (rest) = free to buy. Yellow (hold) = holding stock, waiting for the right sell price. Red (sold) = just sold, mandatory 1-day cooldown. Each day you transition: Green→Yellow (buy), Yellow→Red (sell), Red→Green (cooldown over). You track the best profit in each state.

Algorithm

hold = -prices[0] (bought on day 0), sold = 0, rest = 0.
Each day: newHold = max(hold, rest - price), newSold = hold + price, newRest = max(rest, sold).
Return max(sold, rest) — you shouldn't end holding stock.

🎯 When to recognize this pattern: "Buy/sell stock with constraints (cooldown, fee, k transactions)." Model each constraint as a state. LC 121 (1 transaction), LC 122 (unlimited), LC 123 (at most 2), LC 188 (at most k), LC 714 (with fee). The state machine framework unifies them all.

Why three states suffice: At any point you're either holding (can sell or hold), just sold (forced to rest), or resting (can buy or rest). These three cover all legal positions. Cooldown is enforced by making "sold" transition to "rest" (not directly back to "hold").

Section Four · Trace

Visual Walkthrough

Trace for prices = [1, 2, 3, 0, 2].

Stock Cooldown — State Machine DP

Section Five · Implementation

Code — Java & Python

Java — State machine DP

 class Solution {
public int maxProfit(int[] prices) {
int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < prices.length; i++) {
int newHold = Math.max(hold, rest - prices[i]); // buy or keep int newSold = hold + prices[i]; // sell int newRest = Math.max(rest, sold); // cooldown or stay
hold = newHold; sold = newSold; rest = newRest;
        }
return Math.max(sold, rest);
    }
}

Python — State machine DP

 class Solution:
def maxProfit(self, prices: list[int]) -> int:
        hold, sold, rest = -prices[0], 0, 0 for p in prices[1:]:
            hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
return max(sold, rest)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force recursion	O(3ⁿ)	O(n)	Exponential without memoization
Memoized recursion	O(n)	O(n)	Top-down; 2n states cached
State machine DP ← optimal	O(n)	O(1)	Three variables; clean iterative

Why include rest = max(rest, sold)? After a cooldown day (sold→rest), you can stay in rest for multiple days. max(rest, sold) says: either stay resting, or transition from cooldown (sold yesterday → now free).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single price	`[5]`	Can't sell. max(sold=0, rest=0)=0.
Two prices, rising	`[1,2]`	Buy day 0, sell day 1. Profit=1.
Strictly decreasing	`[5,4,3,2,1]`	Never buy. Profit=0.
Alternating	`[1,4,1,4,1]`	Buy/sell/cool/buy/sell = 3+3 = 6? No — cooldown after first sell. 3+3=6 needs careful check.
All same	`[3,3,3]`	No profit from any trade. Return 0.

⚠ Common Mistake: Not using temp variables for the state transitions. If you update hold before computing sold, the new sold = hold + price uses the wrong (already-updated) hold. Always compute all new values first, then assign. In Python, tuple unpacking handles this automatically.

← Back to DP — 2D problems

LearningTree

LC 309 · Best Time to Buy and Sell Stock with Cooldown — Solution & Explanation | DSA Guide