LeetCode 309 · 2-D DP

Best Time to Buy and Sell Stock with Cooldown, explained with a picture

A trader with three moods: holding, just sold, resting.

Medium2-D DP
▶ Watch it step by step

The problem

Given daily stock prices, maximise profit with as many buy/sell trades as you like, but after you sell you must wait one day (cooldown) before buying again. You can hold at most one share.

Input:  prices = [1, 2, 3, 0, 2]
Output: 3   (buy 1, sell 2, cool down, buy 0, sell 2)

Picture it

Picture a trader who, at the end of every day, is in one of three moods: holding a share, just sold (so must rest tomorrow), or resting (free to buy). Each mood has a number: the best profit possible if you finish the day in that mood. Tomorrow’s numbers come from today’s by following the allowed moves (buy, sell, wait).

How to recognise it

  • You make a sequence of decisions day by day (buy, sell, wait) and want the best total.
  • A rule links neighbouring days: after selling you must wait one day, and you may hold only one share.
  • What you can do today depends only on a small state (holding, just sold, or free), not on the whole history.
  • Up to 5000 days rule out trying every combination of actions.
  • The profit is a number, so you only need the best value for each state, not the trades themselves.

Start with brute force

Walk through the days. On each day, either do nothing, buy (if you hold nothing), or sell (if you hold a share, then skip the next day).

def max_profit_brute(prices):
    n = len(prices)
    def go(day, holding):            # best profit from this day on
        if day >= n:
            return 0
        best = go(day + 1, holding)                         # do nothing
        if holding:
            best = max(best, prices[day] + go(day + 2, False))   # sell, skip a day
        else:
            best = max(best, -prices[day] + go(day + 1, True))   # buy
        return best
    return go(0, False)

Each day branches in two ways, so time is about O(2^n) and space O(n) for the recursion. With n = 5000 that is far beyond reach.

From brute force to the idea

  1. Find the waste. go(day, holding) has only 2n different inputs, but the recursion computes the same pair again and again.
  2. Name the states. At the end of a day you are in exactly one of three states: hold (own a share), sold (just sold today, so tomorrow is a cooldown) or rest (own nothing and free to buy).
  3. Store the best profit for each state. Each variable is the best money you can have if you finish today in that state.
  4. Follow the allowed moves. To hold today, either you already held (hold) or you bought after resting (rest - p). To be in sold today, you held yesterday and sell at today's price p: hold + p. To rest today, you rested or finished a cooldown yesterday: max(rest, sold).
  5. Update all three together. The tuple assignment computes the right-hand sides from yesterday's values, so sold really uses yesterday's hold. Start with hold = -inf because you cannot hold a share before day one.

This is the key idea: three numbers describe every possible situation, and each day they are updated from yesterday's values.

The key idea

State machine DP: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold). O(n).

Python solution

def max_profit(prices):
    hold, sold, rest = -inf, 0, 0
    for p in prices:
        hold, sold, rest = (max(hold, rest - p),   # keep, or buy (only after resting)
                            hold + p,                # sell today
                            max(rest, sold))         # do nothing (cooldown ends)
    return max(sold, rest)

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(2^n): two choices per day without sharing resultsO(n): recursion depth
State machine (shown code)O(n): one pass, three updates per dayO(1): only three variables

Edge cases

  • The shown code needs from math import inf. Without it -inf raises a NameError.
  • Empty list: the loop never runs and the code returns 0.
  • One day ([1]): returns 0, because you cannot sell after buying.
  • Falling prices ([5, 4, 3, 2, 1]): returns 0, since doing nothing beats any trade.
  • Rising prices ([1, 2, 3, 4, 5]): returns 4, one long hold, which the cooldown cannot improve.
  • Cooldown matters ([1, 2, 3, 0, 2]): returns 3. Without the cooldown rule the best is 4, because you could sell on day 3 and buy on the same day.

Common mistakes

  • Starting hold at 0, which pretends you own a free share and overstates profit (see the quiz).
  • Updating the variables one after another, so sold sees today's new hold and the cooldown rule is lost.
  • Returning only sold, which gives a negative number for falling prices instead of 0.
  • Allowing a buy right after a sell by using max(rest, sold) - p for the buy.
Your turn: a fee instead of a cooldown

You may trade as often as you like, but every sale costs a fixed fee. There is no cooldown. For prices [1, 3, 2, 8, 4, 9] and fee 2 the answer is 8. Describe your approach, then write it if you like.

Compare with our answer

Two states are enough now: holding a share and holding none. Selling can happen any day, so there is no "just sold" state; the fee is simply taken off at the sale.

from math import inf

def max_profit_fee(prices, fee):
    hold, cash = -inf, 0
    for p in prices:
        hold, cash = (max(hold, cash - p),        # keep, or buy
                      max(cash, hold + p - fee))  # wait, or sell and pay
    return cash

For the example this returns 8, and [1, 3, 7, 5, 10, 3] with fee 3 returns 6. An empty list returns 0. Time O(n), space O(1).

A strong answer mentions: dropping the third state because nothing forces a wait, charging the fee once per trade, and returning cash.

Check what stuck

1. You may buy and sell as often as you like but can hold at most one share, and every trade costs a fixed fee. Which approach fits best?

2. Why does the shown code compute sold as hold + p using the old hold value?

3. A learner changes the start to hold, sold, rest = 0, 0, 0. What does max_profit([1, 2, 3, 0, 2]) return?

Score 60% or more and the lesson is marked complete.