Best Time to Buy and Sell Stock II (LeetCode 122)
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]71 and sell on day 2 at 5 for +4, then buy on day 3 at 3 and sell on day 4 at 6 for +3. Total 7.prices = [1,2,3,4,5]41 and sell on day 4 at 5 for +4. Selling and buying back every day adds up to the same 4.prices = [7,6,4,3,1]00.⚖️Formal Constraints & Bounds
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Core Insight
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. |
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 at no cost, 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.
🔑 Why It Works
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.
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 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
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
This problem's traps are in Common Pitfalls above.
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.
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)
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.
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.
Best Time to Buy and Sell Stock II (LeetCode 122)
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]71 and sell on day 2 at 5 for +4, then buy on day 3 at 3 and sell on day 4 at 6 for +3. Total 7.prices = [1,2,3,4,5]41 and sell on day 4 at 5 for +4. Selling and buying back every day adds up to the same 4.prices = [7,6,4,3,1]00.⚖️Formal Constraints & Bounds
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Core Insight
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. |
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 at no cost, 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.
🔑 Why It Works
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.
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 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
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
This problem's traps are in Common Pitfalls above.
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.
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)
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.
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.