State machine DP
Track the best result for each possible situation you could be in, and update all of them as you move through a sequence one step at a time.
O(n)Space O(1)6 practice problemsStep-through pictureThe idea
Some problems have rules that depend on what you did before: you can't sell a share you don't hold, or you must rest a day after selling. A state machine lists the situations you can be in, called states, and the moves between them.
State machine DP keeps one number per state: the best result so far if you are in that state right now. At each step of the sequence, every state's new value is computed from the old values of the states that can move into it.
The template is about trading on a price chart with one rule: after you sell, you must wait one day before you buy again. There are three states: holding a share, just sold today, and resting with no share.
An everyday example
A traffic light's day
A traffic light is always green, yellow, or red, and it can only change in fixed ways: green to yellow, yellow to red, red to green. If you wanted to track the best outcome for every possible light color at every minute, you would only need the outcomes from the minute before and the list of allowed changes.
| In the example | In the code |
|---|---|
| The light's colors | The states hold, sold, and rest |
| The allowed color changes | The moves: buy, sell, wait |
| Each minute of the day | Each price in the loop |
| Best outcome while red, say | The value in one state variable |
| Remembering the minute before | prevHold, prevSold, prevRest |
From the slow way to state machine dp
- Start with brute force: on each day, list what you are allowed to do and try every combination. With nothing held you may buy or wait, with a share you may sell or keep it, and the day after a sale you must wait. Over 30 days there are 26,931,732 valid action plans, and over 40 days there are 7,459,895,657.
- Most of those plans are the same in the way that matters. After day 12, the future only depends on two things: which situation you are in (holding, just sold, or free to buy) and how much money you have. Two plans that end day 12 in the same situation face exactly the same choices from then on, so only the richer one is worth keeping.
- So keep one number per situation: the most money you can have if you are in that situation at the end of today. Name the situations:
hold,sold, andrest. Draw arrows for the moves the rules allow:restcan buy intohold,holdcan sell intosold, andsoldcan only move torestthe next day. - For each new price, compute each situation's new value from yesterday's values of the situations with arrows into it, keeping the best. Copy yesterday's values first, so all three updates read the same day. Three numbers carry the whole history forward. That loop is state machine DP.
How it works
- List the states. Here:
hold(I own a share),sold(I sold today), andrest(I own nothing and did not sell today). - Set the starting values. Before the first day you can't hold a share, so
hold = -Infinity;soldandreststart at0. - For each
price, copy the old values intoprevHold,prevSold, andprevRest, so every update reads yesterday's values. holdis the better of keeping the share (prevHold) or buying today fromrest(prevRest - price).soldis selling today:prevHold + price.restis the better of resting again (prevRest) or finishing the cooldown after a sale (prevSold).- At the end, return the better of
soldandrest; ending while holding a share is never better.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function maxProfitWithCooldown(prices) {let hold = -Infinity;let sold = 0;let rest = 0;for (const price of prices) {const prevHold = hold;const prevSold = sold;const prevRest = rest;hold = Math.max(prevHold, prevRest - price);sold = prevHold + price;rest = Math.max(prevRest, prevSold);}return Math.max(sold, rest);}
How fast it is
| Time | O(n) |
|---|---|
| Extra memory | O(1) |
One pass over the prices with three updates per day, keeping only yesterday's three values.
- Best case
O(n)Any list of prices: each day does three updates, whatever the prices are.
- Average case
O(n)Any list: a fixed amount of work per day.
- Worst case
O(n)The same. Even 1,000,000 prices take 1,000,000 passes.
Common mistakes
- Updating
holdand then computingsoldfrom the newhold. Save the previous values first. - Starting
holdat0, which pretends you got a share for free. - Forgetting a state, such as the cooldown, and letting a sale lead straight to a purchase.
- Returning
holdas a possible answer. Owning a share at the end only means you spent money.
When to use it
Look for these clues in a problem:
- What you are allowed to do depends on what you did before (holding or not, cooldown, a mode switch).
- You walk through a sequence (days, characters, events) once and make a decision at each step.
- The problem can be drawn as a few boxes with arrows between them.
- There is a limit on how many times something can happen, which becomes part of the state.
Check yourself
Answer each one in your head first, then open it.
Why must yesterday's values be copied before updating?
sold reads yesterday's hold. If hold were already updated to today's value, the code could buy and sell on the same day.
Why does hold start at -Infinity and not 0?
Owning a share before the first day is impossible. -Infinity makes that situation lose every Math.max until a real purchase happens.
Why is hold never part of the final answer?
Ending with a share means its price was paid and never earned back. Not buying it in the first place would leave more money.
In the trace, why is selling at 6 not the best plan?
Selling at 6 forces a wait on day 5, so the cheap buy at 2 is missed. Selling at 4, waiting on day 4, and trading 2 to 5 makes 3 + 3 = 6 instead of 5.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The loop keeps one promise: after each day, hold, sold, and rest are the most money any valid plan can have if it ends that day in that situation. Before day 1, you own nothing and have 0, so rest is 0 and hold is impossible. sold also starts at 0, which is harmless: it only flows into rest, which is already 0.
Each update keeps the promise. A plan ending today in hold either held yesterday and kept the share, or was in rest yesterday and bought at today's price; those are the only arrows into hold, and the best of each comes from yesterday's best. The same argument covers sold (only from hold, by selling) and rest (from rest by waiting, or from sold after the wait). If a plan reached a situation with less money, swapping in yesterday's best plan for that situation could only do better.
Saving prevHold, prevSold, and prevRest first makes every update read yesterday, not a value already changed today. After the last day, the best plan ends in one of the three situations. Ending in hold means a share was bought and never sold, which is never better, so the answer is the larger of sold and rest.
Going deeper
3 more ideas
What each variable means
After processing a day, hold is the most money you can have (profit so far, counting what you paid) if you own a share at the end of that day. sold is the most if you sold on that day. rest is the most if you own nothing and did not sell that day. Each is one column of a table with a row per day.
Why only cooldown leads to buying
Buying is only allowed from rest. Since sold moves to rest only on the next day, a sale and a new purchase can never happen on neighboring days. The rule of the problem is built into the arrows.
How much work it does
Each day updates a fixed number of states, so the time is O(n) and the space is O(1). With k states it is O(n * k). A limit of k trades turns into 2k states: holding or not, for each trade count.
Work it by hand
Every step in a table, with why
Trade one share over 6 days with a one-day wait after each sale. Each row is one pass of the loop.
prices = [3, 1, 4, 6, 2, 5]
| Step | Day | price | hold | sold | rest | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | start | - | -∞ | 0 | 0 | No share yet | Holding a share before day 1 is impossible, so hold starts at -Infinity. |
| 2 | 1 | 3 | -3 | -∞ | 0 | Buy at 3 is possible | hold is 0 - 3. Selling needs a share from yesterday, so sold stays impossible. |
| 3 | 2 | 1 | -1 | -2 | 0 | Buying at 1 is better | Buying today from rest (0 - 1) beats keeping the share bought at 3. Selling yesterday's share at 1 would lose 2. |
| 4 | 3 | 4 | -1 | 3 | 0 | Sell at 4 for 3 | sold is prevHold + 4 = -1 + 4. rest stays 0, because yesterday's sold was negative. |
| 5 | 4 | 6 | -1 | 5 | 3 | Cooldown after the sale | rest takes yesterday's sold, 3: the wait after selling at 4. Selling at 6 instead would give 5. |
| 6 | 5 | 2 | 1 | 1 | 5 | Buy again at 2 | Buying from rest gives 3 - 2 = 1, better than the old -1. The day-3 sale has finished its wait, so buying is allowed. |
| 7 | 6 | 5 | 1 | 6 | 5 | Sell at 5; loop ends | sold is 1 + 5 = 6. Line 13 returns the larger of sold and rest. |
It returns 6: buy at 1, sell at 4, wait, buy at 2, sell at 5. Holding until 6 would give only 5, because the wait would then block the buy at 2.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| State machine DP | O(n) | O(1) | The default when each day's choices depend on a small, fixed amount of history. |
| Table with a row per day | O(n) | O(n) | You need to rebuild the actual plan by walking back through the days. |
| Sum of every rise (greedy) | O(n) | O(1) | Only when there is no cooldown, no fee, and no trade limit. With a cooldown it can count two trades that aren't allowed together. |
| Try every plan | O(2^n) | O(n) | Only to check answers on 15 days or fewer. |
Extra memory: O(1): six numbers, the three situations and their copies from yesterday. A full table with a row per day would be O(n).
How the steps grow
- State machine DP, Table with a row per day, Sum of every rise (greedy)
O(n) - Try every plan
O(2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| State machine DP | 10 | 1,000 | 1 million |
| Table with a row per day | 10 | 1,000 | 1 million |
| Sum of every rise (greedy) | 10 | 1,000 | 1 million |
| Try every plan | 1,024 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- No prices:
prices = [] - The loop never runs and it returns
Math.max(0, 0), which is 0. - One price:
prices = [8] soldbecomes-Infinityandreststays 0, so it returns 0. You can't buy and sell on one day.- Falling prices:
prices = [9, 7, 4] - Every sale loses money, so
soldstays negative andreststays 0. It returns 0: never trade. - Flat prices:
prices = [5, 5, 5] - Every sale makes exactly 0, so it returns 0.
- Starting
holdat 0 by mistake - That pretends you own a free share. With
prices = [9],soldwould be 9, a profit from nothing.-Infinitymakes the impossible situation lose every comparison.
Variations and follow-ups
Twists interviewers add
No cooldown
Without the wait, sold and rest merge into one situation, "no share", and buying reads yesterday's "no share". This gives the sum of every rise: 8 for this trace's prices.
A fee per trade
Subtract the fee when moving into sold (or into hold, but only one of them). The arrows stay the same. A fee makes small rises not worth trading.
At most k trades
Add the number of trades to the situation: hold[t] and free[t] for t from 0 to k. That is 2k situations, and each day updates all of them, for O(n × k) time.
Other machines
The same pattern fits any rule that depends on recent history: "no three days off in a row" has situations for 0, 1, and 2 days off so far. Pattern matching with * and ? can also be seen as moving between positions in the pattern.
In an interview
Spot it, explain it, answer follow-ups
- Spot it when the rules depend on what you did recently: "after selling you must wait", "you can't do the same thing twice in a row", "at most
ktimes". Each rule becomes a situation and an arrow. - Draw the machine before coding: one circle per situation, one arrow per allowed move, labeled with what it adds or costs. Then each line of code is one circle's update.
- Test tiny price lists by hand: empty, one price, falling prices, and a case where the cooldown changes the answer, like this trace's
[3, 1, 4, 6, 2, 5]. - Expect "what about at most two trades?". Add the trade count to the situation, which gives four situations: first buy, first sell, second buy, second sell.
Where frontend code uses it
The same idea in real UI code
- Trading and analytics dashboards compute "best possible gain" over a price chart with this DP.
- A regular expression engine that tracks a set of possible states after each character updates every state from the states before it, the same step-by-step pattern.
- UI flows with modes, such as an editor in insert or command mode, are state machines; counting or scoring all the ways through them is state machine DP.