Skip to content

Stock Trading

The Problem That Makes You Need This

You're given \(n\) days of stock prices. You can only execute one transaction (buy or sell) per day, but you can hold an unlimited number of shares concurrently. Maximize total profit.

The Greedy Choice: When today's price exceeds the cheapest past price, sell — but push a "fake buy" at today's price so you can extend the trade later if an even better price appears.

This is CF865D (Buy Low, Sell High, rated 2400). The brute force is exponential. DP is \(O(n^2)\). The undo trick solves it in \(O(n \log n)\).

But first, let's see why the obvious approach fails.

The Trap: Selling Too Early

Prices: [10, 20, 30].

Naive greedy scans left to right. Sees 10, buys. Sees 20, sells for +10. Sees 30 — no shares left. Total: 10.

Optimal: buy at 10, sell at 30. Profit = 20.

The greedy committed to selling at 20 and couldn't undo it.

"Wait," you might say, "just buy again at 20 and sell at 30. Profit \(= 10 + 10 = 20\). Same thing!" True for this example. But that observation IS the undo trick — you just haven't formalized it yet.

Now try [10, 25, 15, 30]:

  • Sell at 25: profit 15. Then buy 15, sell 30: profit 15. Total = 30.
  • Or: hold from 10 to 30: profit 20.

The "sell-then-rebuy" strategy actually beats holding. The undo mechanism handles both cases systematically.

Instead of asking "when should I sell?", ask: "what if every sell is provisional, and I can always extend it later?"

The Algorithm: Min-Heap with Fake Buys

Process prices left to right with a min-heap:

For each day with price p:
  1. If heap is non-empty AND heap.top() < p:
     - totalProfit += p - heap.top()
     - Pop the minimum
     - Push p into the heap          (fake buy / undo mechanism)
  2. Push p into the heap              (genuine buy opportunity)

That's the entire algorithm. Six lines of logic. But understanding WHY it works — that's where the real learning is.

Stock price timeline with arrows: solid arrows for buy/sell pairs, dashed arrow showing the fake buy that enables extending a trade to a later, higher price

Why Two Pushes?

Here's something that takes a while to click. When we sell at price \(p_j\) (popping buy price \(p_i\) from the heap), two pushes happen:

  1. Genuine buy (step 2): \(p_j\) enters the heap as a real buy opportunity. Future prices might be even higher.
  2. Fake buy (step 1): \(p_j\) enters the heap as an undo token.

If some future price \(p_k\) pops the fake buy at \(p_j\), the profits telescope:

\[\underbrace{(p_j - p_i)}_{\text{first trade}} + \underbrace{(p_k - p_j)}_{\text{extension}} = p_k - p_i\]

The intermediate \(p_j\) cancels. It's as if we bought at \(p_i\) and sold at \(p_k\) directly. The fake buy at \(p_j\) is the "virtual element" from Lesson 1 — it encodes "reverse this sell and extend the trade."

What Breaks If You Only Push Once?

If you skip the fake buy push, the algorithm can never extend a trade. Prices [1, 5, 10] would give profit 4 (buy 1, sell 5) instead of 9 (buy 1, sell 10). The extension from 5 to 10 requires the fake buy at 5 to be available.

If you skip the genuine buy push, the algorithm can never start a new independent trade at the current price. Prices [1, 5, 2, 10] would miss the trade buy-2-sell-10.

Both pushes are load-bearing.

The Undo Chain in Action

Let's see a case where the undo actually fires. Prices: [1, 5, 10].

Day Price Heap Before \(\text{top} < \text{price}\)? Action Profit
1 1 {} — Push 1 0
2 5 {1} \(1 < 5\): yes Pop 1, profit += 4. Push 5 (fake), push 5 (real) 4
3 10 {5, 5} \(5 < 10\): yes Pop 5, profit += 5. Push 10 (fake), push 10 (real) 9

Profit \(= 9 = 10 - 1\). The algorithm "sold" at 5 (profit 4), then used the fake buy at 5 to "sell" at 10 (profit 5). Net: \(4 + 5 = 9\). The intermediate sell at 5 was undone, and the trade extended from 1 all the way to 10.

Full Trace: 6-Day Example

Prices: [5, 14, 3, 10, 7, 18]. Stare at this table — pay attention to what gets pushed and what sits unused.

Day Price Heap Before (sorted) \(\text{top} < \text{price}\)? Action Profit Heap After
1 5 {} — Push 5 0 {5}
2 14 {5} \(5 < 14\): yes Pop 5, +9. Push 14, 14 9 {14, 14}
3 3 {14, 14} \(14 < 3\): no Push 3 9 {3, 14, 14}
4 10 {3, 14, 14} \(3 < 10\): yes Pop 3, +7. Push 10, 10 16 {10, 10, 14, 14}
5 7 {10, 10, 14, 14} \(10 < 7\): no Push 7 16 {7, 10, 10, 14, 14}
6 18 {7, 10, 10, 14, 14} \(7 < 18\): yes Pop 7, +11. Push 18, 18 27 {10, 10, 14, 14, 18, 18}

Final profit: 27.

Let's verify by hand. The algorithm effectively executed: buy 5 sell 14 (+9), buy 3 sell 10 (+7), buy 7 sell 18 (+11) = 27.

Could we do better? All profitable transactions: buy 5 sell 14, buy 3 sell 10, buy 7 sell 18. Total = 27. No other combination beats this. The algorithm found the optimal.

Notice: The fake buys at 14 and 10 are still in the heap, unused. Not every undo opportunity needs to be taken. The mechanism is there in case it's needed — like an insurance policy that costs nothing if you don't file a claim.

Timeline showing 6 days of prices as a bar chart with buy arrows pointing up at days 1, 3, 5 and sell arrows pointing down at days 2, 4, 6, with dashed undo arrows showing the fake buy mechanism

Connection to Lesson 1

The stock trading undo and the non-adjacent-elements undo are the same idea in different costumes:

Non-Adjacent Elements (L1) Stock Trading (L2)
Pick element \(i\) Sell at price \(p_j\)
Virtual \(V = L + R - i\) Fake buy at \(p_j\)
Picking \(V\) = undo \(i\), pick \(L+R\) Selling later = undo sell at \(j\), extend trade
Max-heap + linked list Min-heap only
\(O(n \log n)\) \(O(n \log n)\)

In both cases:

  1. Make a greedy choice (pick the best available)
  2. Insert an undo token (virtual element / fake buy)
  3. The token's value is designed so picking it later exactly reverses the original choice

The math is always telescoping cancellation: intermediate terms vanish, leaving only the endpoints.

Why It's Optimal

Intuition: At each step, the algorithm takes the maximum available profit margin. The undo mechanism ensures no trade is truly locked in — any sell can be extended later. Since extending a trade from \(p_i \to p_j\) to \(p_i \to p_k\) always increases profit by exactly \(p_k - p_j\), and the fake buy makes this extension available at exactly that cost, no profitable extension is missed.

Formal argument: The algorithm is equivalent to a minimum-cost flow on a DAG where each day is a node, with edges encoding buy/sell/hold decisions. The min-heap greedily augments along shortest paths, which is optimal for unit-capacity flow networks.

Variations

Multiple Shares Per Day

If you can buy/sell up to \(m\) shares per day, push the price \(m\) times as genuine buy opportunities. The undo mechanism stays the same.

Transaction Fees

If each transaction costs a fee \(f\), only sell when currentPrice - minPriceHeap.top() > f. The full integration of fees into the 6-line greedy requires careful bookkeeping of whether the fee is charged on buy or sell — this is better handled with DP/state-machine approaches (LeetCode 714) for correctness.

At Most K Transactions

This variant (LeetCode 188) is better handled with WQS Binary Search (Chapter 7) or DP, but the undo intuition applies: WQS penalizes each transaction by \(\lambda\), and greedy-with-undo finds the optimal count for each \(\lambda\).

Complexity

  • Time: \(O(n \log n)\). Each day does at most one pop and two pushes, each \(O(\log n)\).
  • Space: \(O(n)\) for the heap.

Try It

Exercise 1 (predict first): Prices = [8, 2, 5, 1, 9, 3, 7]. Before tracing, predict: which price does the algorithm sell at first? What's the fake buy value?

Now trace the full algorithm. Fill in every row:

Day Price Heap Before Action Profit
1 8
2 2
3 5
4 1
5 9
6 3
7 7

Verify your answer matches the optimal profit you can compute by exhaustive search.

Exercise 2 (the boring case): Prices = [10, 8, 5, 3, 1] — strictly decreasing. What does the heap look like at the end? Why is the profit 0? Does the algorithm ever try to sell?

Challenge: Prices = [1, 2, 3, 4, 5] — strictly increasing. The algorithm sells on every day after the first. Trace it carefully: on day 4 the algorithm pops the fake buy at 2 (not 1), giving profit \((4-2)=2\). The total is 6, not 4. Why? Because you can hold multiple shares — buy on days 1 and 2, sell on days 4 and 5, profit \(= (4-1) + (5-2) = 6\). Verify this by tracing the heap state after each day.

Problems

Problem Link Difficulty
CF865D — Buy Low, Sell High codeforces.com/problemset/problem/865/D 2400
LeetCode 122 — Best Time to Buy and Sell Stock II leetcode.com/problems/best-time-to-buy-and-sell-stock-ii Medium
LeetCode 188 — Best Time to Buy and Sell Stock IV leetcode.com/problems/best-time-to-buy-and-sell-stock-iv Hard
LC 714 — Buy/Sell Stock with Transaction Fee leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee Medium
LC 502 — IPO leetcode.com/problems/ipo Hard