p03 Best Time to Buy/Sell Stock — Progressive Hints

One hint at a time. 5-min timer between hints.

Hint 1 — Reframe the problem

You’re searching for the maximum of prices[j] - prices[i] over all valid (i, j) with i < j. That’s a 2D search. Can you reduce one dimension by asking: “for a fixed j, what is the best i?”

Hint 2 — What helps at each j

For each candidate sell-day j, the most profitable buy-day is whichever earlier day had the lowest price. So at each j, you only need to know one thing about the past: the minimum price among days 0..j-1.

Hint 3 — The key insight

Walk left to right. Maintain min_so_far = minimum of all prices seen before today. For each price today: candidate profit is price - min_so_far; update the running best. Then update min_so_far with today’s price.

This makes the algorithm O(N) time and O(1) space.

Hint 4 — Pseudocode

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

Pay attention to the order of those two updates inside the loop. One order is right, the other has a subtle bug visible only on harder follow-ups.

Hint 5 — Full algorithm + order rationale

Initialize min_so_far = +∞ (so the first iteration’s price - min_so_far is very negative and doesn’t pollute best, which starts at 0). For each price:

  1. First: compute best = max(best, price - min_so_far). This uses the min from STRICTLY BEFORE today — we cannot sell on the same day we buy.
  2. Then: update min_so_far = min(min_so_far, price). Now today’s price becomes available for future sell-days.

If you reverse the order (update min first, then compute best), you’d compute price - price = 0 on the day a new min appears, which is harmless here but causes phantom self-trades on the multi-transaction variants. Get the discipline right now.

The correctness proof: for any optimal pair (i*, j*), when the loop reaches j*, min_so_far ≤ prices[i*] (because i* < j*). So the algorithm sees at least the optimal profit, and we take the max, so we capture it.

Time O(N), Space O(1).