p03 — Best Time to Buy and Sell Stock

Source: LeetCode 121 · Easy · Topics: Array, DP, Greedy Companies: Amazon (very high), Bloomberg (very high), Facebook (high), Apple (medium), Uber (medium) Loop position: phone screen, or first warmup before harder DP onsite

1. Quick Context

This is the “single-transaction maximum profit” problem and the entry door to a 6-problem ladder (LC 121, 122, 123, 188, 309, 714) that culminates in the hardest stock problems on LC. Mastering p03 properly — by recognizing it as “max forward-difference with constraint i < j” and NOT brute force — unlocks the whole family.

What it looks like it tests: array iteration. What it actually tests: Whether you see the invariant transformation: instead of trying all (buy, sell) pairs, track the minimum buy-price seen-so-far and compute profit-if-sold-today. This is a one-pass O(N), O(1) algorithm; the brute force is O(N²).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

12-min timer. Cold attempt. No reading on.

3. Prerequisite Concepts

• “Running min/max” pattern — phase-02 §3 Prefix Sums (same family — running aggregate)
• Greedy correctness: why local-min + global-max-of-(today - min) is globally optimal

4. How to Approach

Restate: Given prices indexed by day, pick a buy-day i and a sell-day j > i to maximize prices[j] - prices[i]. If no profit possible, return 0. One transaction only.

Clarify:

• “Can I sell on the same day I buy?” (No — strict j > i.)
• “If prices monotonically decrease, return 0 or negative?” (Per LC: 0 — no transaction is valid.)
• “Multiple transactions allowed?” (No, this is LC 121. LC 122 is the multi-transaction version. ASK to confirm.)
• “Length bounds?” (LC: up to 10⁵ → O(N²) will TLE.)

Examples:

• [7,1,5,3,6,4] → 5 (buy at 1, sell at 6)
• [7,6,4,3,1] → 0 (no profit possible)
• [1] → 0 (no transaction possible — single price)
• [2,4,1] → 2 (buy at 2, sell at 4, NOT buy at 1; can’t sell after — common trap)

Brute force: All (i, j) pairs with j > i; track max diff. O(N²) time, O(1) space.

Pattern recognition: “Max value of a[j] - a[i] with i < j” → equivalent to “at each j, what’s the min of a[0..j-1]?” → running-min + per-element subtract → O(N).

Optimal:

min_so_far = +infinity
best = 0
for price in prices:
    best = max(best, price - min_so_far)
    min_so_far = min(min_so_far, price)
return best

Order matters: Compute best BEFORE updating min_so_far. Otherwise on a single day you’d allow “buy and sell same day” (price - price = 0, no harm here but ON LC 122 the equivalent bug causes phantom profits).

Correctness proof (greedy): For any optimal pair (i*, j*) with j* > i*, when the loop reaches j*, min_so_far ≤ prices[i*] (because i* ≤ j*-1, and min_so_far covers prices[0..j*-1]). So prices[j*] - min_so_far ≥ prices[j*] - prices[i*] = optimal. Since we take the max over all j, we capture this value.

5. Progressive Hints

hints.md — one at a time, 5-min timer.

6. Deeper Insight — Why It Works

The transformation: A 2D search “find (i, j) max difference” becomes 1D “at each j, what’s the best historical min?” by recognizing that for any fixed j, the optimal i is argmin(prices[0..j-1]). We don’t need to remember which i — just its value. This is the same compression that powers Kadane’s algorithm (maximum subarray): instead of trying all subarrays, track the best one ending here.

Why O(1) space: The running-min subsumes all history we need. We never look back; we only look at the current price vs. the cheapest ever.

Connection to Kadane’s algorithm: If you compute diffs[i] = prices[i+1] - prices[i], then LC 121 becomes “max sum subarray over diffs” — Kadane’s algorithm. This equivalence is a Staff-level observation.

7. Anti-Pattern Analysis

Wrong #1 — Two pointers from both ends: Some try left = 0, right = N-1, shrink to find max. Doesn’t work: the optimal pair isn’t necessarily at the extremes.

Wrong #2 — Sort: Sorting destroys the time-order constraint. The buy-day must come before the sell-day in original order.

Wrong #3 — Update min before max:

for p in prices:
    min_so_far = min(min_so_far, p)   # ← wrong order
    best = max(best, p - min_so_far)

On LC 121, gives same answer because max profit on day i if buy=sell=i is 0. But on the multi-tx variants this exact bug allows “buy and sell at same instant,” inflating profit.

Wrong #4 — Greedy “buy every local min”: Confuses LC 121 (single transaction) with LC 122 (multiple). Read the prompt.

8. Skills & Takeaways

Pattern: running-min/max + per-element decision. Direct applications:

• LC 122 — Buy/Sell II (multiple tx → sum positive diffs greedily)
• LC 123 — Buy/Sell III (at most 2 tx → DP over states)
• LC 188 — Buy/Sell IV (at most k tx → generalized DP)
• LC 309 — with cooldown (state machine DP)
• LC 714 — with fee (state machine DP)
• LC 53 — Maximum Subarray (Kadane — same family via diff transform)
• LC 152 — Maximum Product Subarray (track both running min and max because negatives)

9. When to Move On

• Solved unaided <8 min, O(N), O(1)
• Tested decreasing input, single-element, two-element
• Articulated the “running min + per-step profit” transformation
• Connected to Kadane’s algorithm via the diff trick
• Stress test passes
• Solved LC 122, LC 53; saw the family resemblance

10. Company Context

Amazon

• The framing: “You’re shown daily stock prices for a company. What’s the most an investor could have made with one buy and one sell?”
• Misleading example: They give [2, 4, 1] to bait the “buy at 1” mistake. The trap: 1 is the LAST day, no sell possible after.
• Adversarial extension: “Now they can do multiple transactions” (→ LC 122) immediately followed by “now there’s a $1 fee per transaction” (→ LC 714). Tests whether you generalize cleanly.

Bloomberg (terminal company — they LIVE on time-series)

• The framing: Often pure LC 121, sometimes with timestamps not indices (test if you read the order from the input).
• What they want: Recognition that this is a time-series invariant problem. The phrase “I’ll track the running minimum” is a green check.
• Extension: “What if prices stream in?” → same algorithm; the running-min works incrementally.

Meta

• The framing: Followed RAPIDLY by LC 122, then “at most k transactions” (LC 188).
• What they want: You finish LC 121 in 5 minutes so they get to LC 188. If you spend 15 min on LC 121, you’ll never reach the real interview question.

Uber

• Frame: “Surge pricing history — best moment to launch a promotional ride.”
• Extension: “What if some days are weekends and weekend buys are forbidden?” → tests masking, not algorithm.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Now allow unlimited transactions.” → LC 122.

Answer: Sum every positive consecutive diff: sum(max(0, prices[i+1] - prices[i]) for i in range(N-1)). Proof: any concave-up segment between local min and local max contributes (max - min); the sum of positive diffs equals the sum of these contributions. O(N) one pass, O(1) space.

Q2: “At most k transactions.” → LC 188.

Answer: DP. State: dp[t][i] = max profit using ≤ t transactions through day i. Transition: dp[t][i] = max(dp[t][i-1], max over j<i of (dp[t-1][j-1] + prices[i] - prices[j])). Naively O(k·N²); optimize the inner max to O(1) by tracking max(dp[t-1][j-1] - prices[j]) as we scan, giving O(k·N). When k ≥ N/2, problem degenerates to unlimited tx (LC 122) — handle this case separately.

Q3: “What about transaction fee f per buy-sell pair?” → LC 714.

Answer: State machine. hold[i] = max profit ending day i holding a stock; cash[i] = max profit ending day i not holding. hold[i] = max(hold[i-1], cash[i-1] - prices[i]). cash[i] = max(cash[i-1], hold[i-1] + prices[i] - f). Pay the fee when selling. O(N), O(1) with two scalars.

Q4: “Streaming prices, infinite stream. Output the running best-possible-profit-so-far.”

Answer: Same algorithm, incremental. Maintain min_so_far and best. On each tick, update both. The answer is best at all times. O(1) per tick.

Q5: “How do you test it?”

Answer: (1) Edge: empty (or N=1) → 0, decreasing → 0, increasing → last - first. (2) Property: brute-force O(N²) vs optimal on random arrays. (3) Adversarial: arrays where the buy is on day 0 vs day N-2 — tests whether running-min update timing is right.

14. Full Solution Walkthrough

See solution.py.

Three solutions for didactic value:

• max_profit_brute: all pairs, O(N²). Oracle.
• max_profit: running-min one-pass, O(N), O(1).
• max_profit_kadane: Kadane on diffs, to demonstrate equivalence.

All three should agree under stress_test.

15. Beyond the Problem

Real systems this is the kernel of:

• Backtest engines (Zipline, Backtrader): the “perfect foresight” upper bound used to score strategies. A strategy can’t beat single-transaction-max-profit on a sequence; this is the benchmark.
• A/B test analysis: “what’s the largest sustained delta we observed?” — same running-min/max.
• Latency/throughput dashboards: “what’s the largest drop in throughput?” — running-max + per-point delta.

Principal-engineer code review comment: “This algorithm assumes prices is a value-typed array. In our pipeline, prices are timestamped events with possible gaps. Either resample to fixed-interval before feeding, or change the algorithm to work on (timestamp, price) tuples and handle missing intervals. Also: what’s the contract when prices contains NaN (market closed)? Define it explicitly.”