Best Time to Buy and Sell Stock II (LeetCode 122)
You will see how two running states, owning a share or not, capture every buy-and-sell plan in one pass.
You get an integer array prices: on day i, one share of a stock costs prices[i]. On each day you may buy a share, sell the share you own, or both, but you can never own more than one share at a time. Selling and then buying again on the same day is allowed, and there is no limit on the number of trades.
Return the largest total profit you can make. If no trade helps, the answer is 0.
Worked Examples
prices = [7,1,5,3,6,4]7prices = [1,2,3,4,5]4prices = [7,6,4,3,1]0⚖️Formal Constraints & Bounds
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Why It Works & Core Invariant
Only two facts matter at the end of a day: whether you own a share, and the best profit for each case. Each day's two values come from yesterday's two, so one pass finds the best plan.
Real-World Scenario & Production Applications
Any system that moves between a few modes step by step, and pays or earns on each switch: a battery that charges or discharges against hourly power prices, a machine that runs or idles, a position that is open or closed. Keeping the best value for each mode finds the best plan in one pass.
Step-by-Step Execution Trace Table
Day i | p | hold = max(hold, cash - p) | cash = max(cash, hold + p) | What the states mean |
|---|---|---|---|---|
| 0 | 7 | -7 (start) | 0 (start) | Bought on day 0 / own nothing |
| 1 | 1 | max(-7, 0 - 1) = -1 | max(0, -7 + 1) = 0 | Buying at 1 beats keeping the share bought at 7 |
| 2 | 5 | max(-1, 0 - 5) = -1 | max(0, -1 + 5) = 4 | Selling at 5 locks in +4 |
| 3 | 3 | max(-1, 4 - 3) = 1 | max(4, -1 + 3) = 4 | Buy again at 3 with the 4 in hand |
| 4 | 6 | max(1, 4 - 6) = 1 | max(4, 1 + 6) = 7 | Selling at 6 adds +3 |
| 5 | 4 | max(1, 7 - 4) = 3 | max(7, 1 + 4) = 7 | Nothing beats 7; return cash = 7 |
| 1 | At the end of each day you either own one share (`hold`) or none (`cash`): keep the best profit for each state. |
| 2 | `hold = max(hold, cash - p)` keeps the share or buys today; `cash = max(cash, hold + p)` stays out or sells today. Both read yesterday's values. |
| 3 | Start `hold = -prices[0]` and `cash = 0`, update both once for every later day with one tuple assignment, then `return cash`. |
| 4 | The trap: `hold` starts at `-prices[0]`, not `0`, or `cash` sells a share you never paid for. |
Target: Best Time to Buy and Sell Stock II (LeetCode 122). Owning a share on day 0 means we paid prices[0] for it. Starting at 0 would be a free share that cash could sell.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A trading plan looks like a huge search: on every day you could buy, sell or wait, so there are exponentially many plans. State Machine DP collapses it. At the end of any day you are in exactly one of two states: you own a share (hold) or you don't (cash). Tomorrow's best profit in each state depends only on today's two numbers, never on how you got there. So you carry two numbers through the array and update them once per day.
🏟️ The Analogy: A Light Switch With a Price Tag
Picture a switch that is either on (you own a share) or off (you don't). Each day the switch can stay where it is for free, or flip: flipping on costs today's price, flipping off pays today's price. You don't need to remember the whole history of flips; you only need the best balance you could have right now with the switch on, and the best balance with it off.
🪄 The Mathematical Harmony / Magic Trick
hold = -prices[0] # switch on day 0: we paid for the sharecash = 0 # switch off: nothing spentfor i in range(1, len(prices)): p = prices[i] hold, cash = max(hold, cash - p), max(cash, hold + p)return cash The tuple assignment evaluates both right-hand sides with yesterday's hold and cash before either changes. Every legal plan is a path of switch flips, and each max keeps only the best way to arrive at a state, so the final cash is the best plan of all.
💡 Summary
Name the states, write one line per allowed move, update from yesterday's values, and start from a state you can actually be in (hold = -prices[0]). Extra rules (a fee, a cooldown, a trade limit) become an extra term or an extra state, not a new algorithm. One pass: time, space.
Starting
holdat0:hold = 0means owning a share you never paid for, so on day 1cash = max(0, 0 + p)sells it for a free profit. On[7,1,5,3,6,4]that returns8instead of7. Start withhold = -prices[0].Reading a value that already changed today: the tuple assignment
hold, cash = max(hold, cash - p), max(cash, hold + p)computes both right-hand sides from yesterday's values. In this problem two separate lines happen to give the same answer, but with a fee or a cooldown they don't, so build the habit here.Returning
max(hold, cash): holding a share at the end means money was spent on something never sold;cashis always at least as large, so returncash.Treating it as "one best trade": that is Best Time to Buy and Sell Stock (LC 121). Here trades are unlimited, so every profitable rise can be taken, and the state machine takes them all automatically.
4-Phase Thought Process Model
You will see how a senior engineer spots a two-state machine behind a trading question and defends it out loud.
Pattern Recognition Signals
The 10-second spot
"Buy and sell as many times as you like" and "own at most one share at a time": at the end of every day you are in one of two modes (own a share or not), and each day's choices depend only on that mode. A few modes with day-by-day moves between them is the signal for State Machine DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each day, hold is the best profit so far while owning one share and cash the best profit so far while owning none: hold = max(hold, cash - p) (keep or buy) and cash = max(cash, hold + p) (keep or sell), both reading yesterday's values.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
hold = -prices[0], not0: starting at 0 means owning a share for free, andcashthen sells it (on[7,1,5,3,6,4]the answer comes out8instead of7).Read yesterday's values:
hold, cash = max(hold, cash - p), max(cash, hold + p)evaluates both right-hand sides before assigning. Here the order happens not to matter, but with a cooldown or a fee, two separate lines read a value that already changed today.return cash, notmax(hold, cash): ending the last day with a share never beats selling it or never buying it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with State Machine DP. At the end of any day I'm in one of two states: I own a share, or I don't. I keep the best profit for each, hold and cash. Each new price allows two moves: hold becomes the better of keeping my share or buying today out of cash, and cash becomes the better of staying out or selling today out of hold. I compute both from yesterday's values in one tuple assignment. It's correct because every legal plan of trades is a path through these two states, and each update keeps the best way to reach each state. The trap is the start: hold must be minus the first price, not zero, or I'd sell a share I never paid for. At the end I return cash, since ending with a share is never better. One pass, so
O(N)time andO(1)space.
So: name the states hold and cash, write one line per move, start hold at -prices[0], and return cash.
Complexity & Mathematical Proof
O(N)
Look at the code: after setting hold and cash, the loop for i in range(1, len(prices)) runs once for each of the other N - 1 days, and its body reads one price and does one tuple assignment with two max calls, a constant amount of work. Total: O(N).
O(1)
The code keeps only hold, cash, i and p, whatever the input size, and returns one integer: O(1) extra space.
T(N) = O(1) + (N - 1) · O(1) = O(N)
Look at the code: after setting hold and cash, the loop for i in range(1, len(prices)) runs once for each of the other N - 1 days, and its body reads one price and does one tuple assignment with two max calls, a constant amount of work. Total: O(N).
Derivation Progression
O(1)
hold = -prices[0] and cash = 0 are two assignments.
(N - 1) iterations
for i in range(1, len(prices)) visits every day after day 0 exactly once.
O(1) per iteration
One tuple assignment with two max calls, whatever N is.
O(N)
Constant work per day over N days.
Variable Definitions
Number of days, len(prices)
Today's price, prices[i]
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): hold, cash, i, p
O(1): one integer
Boundary Best / Worst Cases
: every day is visited even when prices only fall
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "trade as many times as you like", "never own more than one share". Every day ends in one of two modes, owning a share or not, and the next day's options depend only on the mode: State Machine DP with states hold and cash.
days, prices . The profit is at most the sum of all rises, below , so it fits a 32-bit integer. Budget: time, space; the loop also works on a live price stream, since it keeps no history.
Starting hold at 0 creates a free share. In a streaming service, the state is only two numbers, but it must be updated once per price in order: replaying or reordering ticks changes the answer, so process each tick exactly once.
Core Algorithmic State Invariants
After each day, `hold` is the best profit so far while owning one share and `cash` the best profit so far while owning none. No other fact about the past can change a future decision.
`hold = max(hold, cash - p)` and `cash = max(cash, hold + p)` both read yesterday's values (one tuple assignment). Every legal plan is a path through the two states, and each `max` keeps the best way to arrive.
The start must be a state you can really be in: `hold = -prices[0]`, `cash = 0`. One O(1) update per day gives O(N) time and O(1) space, and the answer is the final `cash`.
Best Time to Buy and Sell Stock II (LeetCode 122)
You will see how two running states, owning a share or not, capture every buy-and-sell plan in one pass.
You get an integer array prices: on day i, one share of a stock costs prices[i]. On each day you may buy a share, sell the share you own, or both, but you can never own more than one share at a time. Selling and then buying again on the same day is allowed, and there is no limit on the number of trades.
Return the largest total profit you can make. If no trade helps, the answer is 0.
Worked Examples
prices = [7,1,5,3,6,4]7prices = [1,2,3,4,5]4prices = [7,6,4,3,1]0⚖️Formal Constraints & Bounds
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Why It Works & Core Invariant
Only two facts matter at the end of a day: whether you own a share, and the best profit for each case. Each day's two values come from yesterday's two, so one pass finds the best plan.
Real-World Scenario & Production Applications
Any system that moves between a few modes step by step, and pays or earns on each switch: a battery that charges or discharges against hourly power prices, a machine that runs or idles, a position that is open or closed. Keeping the best value for each mode finds the best plan in one pass.
Step-by-Step Execution Trace Table
Day i | p | hold = max(hold, cash - p) | cash = max(cash, hold + p) | What the states mean |
|---|---|---|---|---|
| 0 | 7 | -7 (start) | 0 (start) | Bought on day 0 / own nothing |
| 1 | 1 | max(-7, 0 - 1) = -1 | max(0, -7 + 1) = 0 | Buying at 1 beats keeping the share bought at 7 |
| 2 | 5 | max(-1, 0 - 5) = -1 | max(0, -1 + 5) = 4 | Selling at 5 locks in +4 |
| 3 | 3 | max(-1, 4 - 3) = 1 | max(4, -1 + 3) = 4 | Buy again at 3 with the 4 in hand |
| 4 | 6 | max(1, 4 - 6) = 1 | max(4, 1 + 6) = 7 | Selling at 6 adds +3 |
| 5 | 4 | max(1, 7 - 4) = 3 | max(7, 1 + 4) = 7 | Nothing beats 7; return cash = 7 |
| 1 | At the end of each day you either own one share (`hold`) or none (`cash`): keep the best profit for each state. |
| 2 | `hold = max(hold, cash - p)` keeps the share or buys today; `cash = max(cash, hold + p)` stays out or sells today. Both read yesterday's values. |
| 3 | Start `hold = -prices[0]` and `cash = 0`, update both once for every later day with one tuple assignment, then `return cash`. |
| 4 | The trap: `hold` starts at `-prices[0]`, not `0`, or `cash` sells a share you never paid for. |
Target: Best Time to Buy and Sell Stock II (LeetCode 122). Owning a share on day 0 means we paid prices[0] for it. Starting at 0 would be a free share that cash could sell.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A trading plan looks like a huge search: on every day you could buy, sell or wait, so there are exponentially many plans. State Machine DP collapses it. At the end of any day you are in exactly one of two states: you own a share (hold) or you don't (cash). Tomorrow's best profit in each state depends only on today's two numbers, never on how you got there. So you carry two numbers through the array and update them once per day.
🏟️ The Analogy: A Light Switch With a Price Tag
Picture a switch that is either on (you own a share) or off (you don't). Each day the switch can stay where it is for free, or flip: flipping on costs today's price, flipping off pays today's price. You don't need to remember the whole history of flips; you only need the best balance you could have right now with the switch on, and the best balance with it off.
🪄 The Mathematical Harmony / Magic Trick
hold = -prices[0] # switch on day 0: we paid for the sharecash = 0 # switch off: nothing spentfor i in range(1, len(prices)): p = prices[i] hold, cash = max(hold, cash - p), max(cash, hold + p)return cash The tuple assignment evaluates both right-hand sides with yesterday's hold and cash before either changes. Every legal plan is a path of switch flips, and each max keeps only the best way to arrive at a state, so the final cash is the best plan of all.
💡 Summary
Name the states, write one line per allowed move, update from yesterday's values, and start from a state you can actually be in (hold = -prices[0]). Extra rules (a fee, a cooldown, a trade limit) become an extra term or an extra state, not a new algorithm. One pass: time, space.
Starting
holdat0:hold = 0means owning a share you never paid for, so on day 1cash = max(0, 0 + p)sells it for a free profit. On[7,1,5,3,6,4]that returns8instead of7. Start withhold = -prices[0].Reading a value that already changed today: the tuple assignment
hold, cash = max(hold, cash - p), max(cash, hold + p)computes both right-hand sides from yesterday's values. In this problem two separate lines happen to give the same answer, but with a fee or a cooldown they don't, so build the habit here.Returning
max(hold, cash): holding a share at the end means money was spent on something never sold;cashis always at least as large, so returncash.Treating it as "one best trade": that is Best Time to Buy and Sell Stock (LC 121). Here trades are unlimited, so every profitable rise can be taken, and the state machine takes them all automatically.
4-Phase Thought Process Model
You will see how a senior engineer spots a two-state machine behind a trading question and defends it out loud.
Pattern Recognition Signals
The 10-second spot
"Buy and sell as many times as you like" and "own at most one share at a time": at the end of every day you are in one of two modes (own a share or not), and each day's choices depend only on that mode. A few modes with day-by-day moves between them is the signal for State Machine DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each day, hold is the best profit so far while owning one share and cash the best profit so far while owning none: hold = max(hold, cash - p) (keep or buy) and cash = max(cash, hold + p) (keep or sell), both reading yesterday's values.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
hold = -prices[0], not0: starting at 0 means owning a share for free, andcashthen sells it (on[7,1,5,3,6,4]the answer comes out8instead of7).Read yesterday's values:
hold, cash = max(hold, cash - p), max(cash, hold + p)evaluates both right-hand sides before assigning. Here the order happens not to matter, but with a cooldown or a fee, two separate lines read a value that already changed today.return cash, notmax(hold, cash): ending the last day with a share never beats selling it or never buying it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with State Machine DP. At the end of any day I'm in one of two states: I own a share, or I don't. I keep the best profit for each, hold and cash. Each new price allows two moves: hold becomes the better of keeping my share or buying today out of cash, and cash becomes the better of staying out or selling today out of hold. I compute both from yesterday's values in one tuple assignment. It's correct because every legal plan of trades is a path through these two states, and each update keeps the best way to reach each state. The trap is the start: hold must be minus the first price, not zero, or I'd sell a share I never paid for. At the end I return cash, since ending with a share is never better. One pass, so
O(N)time andO(1)space.
So: name the states hold and cash, write one line per move, start hold at -prices[0], and return cash.
Complexity & Mathematical Proof
O(N)
Look at the code: after setting hold and cash, the loop for i in range(1, len(prices)) runs once for each of the other N - 1 days, and its body reads one price and does one tuple assignment with two max calls, a constant amount of work. Total: O(N).
O(1)
The code keeps only hold, cash, i and p, whatever the input size, and returns one integer: O(1) extra space.
T(N) = O(1) + (N - 1) · O(1) = O(N)
Look at the code: after setting hold and cash, the loop for i in range(1, len(prices)) runs once for each of the other N - 1 days, and its body reads one price and does one tuple assignment with two max calls, a constant amount of work. Total: O(N).
Derivation Progression
O(1)
hold = -prices[0] and cash = 0 are two assignments.
(N - 1) iterations
for i in range(1, len(prices)) visits every day after day 0 exactly once.
O(1) per iteration
One tuple assignment with two max calls, whatever N is.
O(N)
Constant work per day over N days.
Variable Definitions
Number of days, len(prices)
Today's price, prices[i]
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): hold, cash, i, p
O(1): one integer
Boundary Best / Worst Cases
: every day is visited even when prices only fall
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "trade as many times as you like", "never own more than one share". Every day ends in one of two modes, owning a share or not, and the next day's options depend only on the mode: State Machine DP with states hold and cash.
days, prices . The profit is at most the sum of all rises, below , so it fits a 32-bit integer. Budget: time, space; the loop also works on a live price stream, since it keeps no history.
Starting hold at 0 creates a free share. In a streaming service, the state is only two numbers, but it must be updated once per price in order: replaying or reordering ticks changes the answer, so process each tick exactly once.
Core Algorithmic State Invariants
After each day, `hold` is the best profit so far while owning one share and `cash` the best profit so far while owning none. No other fact about the past can change a future decision.
`hold = max(hold, cash - p)` and `cash = max(cash, hold + p)` both read yesterday's values (one tuple assignment). Every legal plan is a path through the two states, and each `max` keeps the best way to arrive.
The start must be a state you can really be in: `hold = -prices[0]`, `cash = 0`. One O(1) update per day gives O(N) time and O(1) space, and the answer is the final `cash`.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Start in a state you can really be in: bought on day 0 | hold = -prices[0] | Owning a share on day 0 means we paid prices[0] for it. Starting at 0 would be a free share that cash could sell. |
| Start the no-share state with nothing spent | cash = 0 | Not buying at all is always allowed, so the best no-share profit starts at 0 and never drops below it. |
| Visit each later day once | for i in range(1, len(prices)):
p = prices[i] | Day 0 is already in the start values; every other day gets exactly one update. |
| One line per allowed move, all reading yesterday's states | hold, cash = max(hold, cash - p), max(cash, hold + p) | hold keeps its share or buys from cash; cash stays out or sells from hold. The tuple assignment reads both old values before changing either. |
| Answer from the final no-share state | return cash | Ending the last day still owning a share is never better than having sold it or never bought it. |