Best Time to Buy and Sell Stock with Cooldown

The problem. prices[i] is a stock's price on day i. Make as many buy-then-sell transactions as you like, holding at most one share at a time — but after you sell, you can't buy on the next day (a one-day cooldown). Return the maximum profit.

Example

prices = [1, 2, 3, 0, 2]  ->  3   (buy 1, sell 2, cooldown, buy 0, sell 2)
prices = [1]              ->  0
prices = [3, 2, 1]        ->  0   (never buy)
prices = [1, 4, 2]        ->  3   (buy 1, sell 4)

The idea: name the states, then the moves between them

At the end of each day you're in exactly one of three situations: hold (you own a share), sold (you sold today, so tomorrow is a cooldown) or rest (no share and free to buy). Keep the best profit for each. The moves between them are the whole problem:

The answer is the better of ending in sold or rest — never in hold, since a share you still own earned nothing. This state machine view works for the whole stock family: add a fee, cap the transactions, and so on.

1. Plain recursion: what to do today

1function maxProfit(prices) {2  const best = (day, holding) => {               // the most profit from day on3    if (day >= prices.length) return 0;4    const wait = best(day + 1, holding);         // do nothing today5    if (holding) return Math.max(wait, prices[day] + best(day + 2, false));   // sell; tomorrow is cooldown6    return Math.max(wait, -prices[day] + best(day + 1, true));               // buy7  };8  return best(0, false);9}

Time O(2ⁿ), space O(n). Selling jumps two days ahead — that's the cooldown, built into the recursion. But there are only 2n different (day, holding) pairs.

2. Memoize (day, holding)

1function maxProfit(prices) {2  const memo = new Map();                        // day * 2 + holding -> best profit3  const best = (day, holding) => {4    if (day >= prices.length) return 0;5    const key = day * 2 + (holding ? 1 : 0);6    if (memo.has(key)) return memo.get(key);7    let result = best(day + 1, holding);         // do nothing today8    if (holding) result = Math.max(result, prices[day] + best(day + 2, false));   // sell; tomorrow is cooldown9    else result = Math.max(result, -prices[day] + best(day + 1, true));          // buy10    memo.set(key, result);11    return result;12  };13  return best(0, false);14}

Time O(n), space O(n). The recursion goes up to n calls deep; with LeetCode's 5,000 days that's past Python's default limit of 1,000 frames. The three-state loop below has no such limit.

3. Three states, three variables

1function maxProfit(prices) {2  let hold = -prices[0], sold = 0, rest = 0;     // best profit ending the day holding / having just sold / resting3  for (const p of prices) {4    const prevSold = sold;5    sold = hold + p;                             // sell the share we held6    hold = Math.max(hold, rest - p);             // keep it, or buy: only from rest, never right after a sale7    rest = Math.max(rest, prevSold);             // yesterday's sale makes today a cooldown8  }9  return Math.max(sold, rest);10}

Time O(n), space O(1). The order matters: sold and hold both read yesterday's hold, and rest reads yesterday's sold, so update sold before hold and save the old sold first. Starting with hold = -prices[0] means "bought on day 0"; selling it the same day just gives 0.

Comparing the approaches

Edge cases to test

Variations