Best Time to Buy and Sell Stock
easyTime: O(n)Space: O(1)
The shape of the problem
Given a list of daily prices, return the maximum profit from buying on one day and selling on a later day. If no profitable pair exists, return 0.
Signals to notice
max over a running baselineone transactionleft-to-right sweep
Brute force first
Try every (buy, sell) pair: O(n²). Correct but recomputes minimums over and over.
The key insight
For any day i picked as the sell day, the best buy day is the cheapest day in `0..i-1`. That cheapest-so-far value can be maintained in O(1) per step as you scan.
Trace it on prices=[7,1,5,3,6,4]
p=7 min=7 profit=7-7=0 best=0 p=1 min=1 profit=1-1=0 best=0 p=5 min=1 profit=5-1=4 best=4 p=3 min=1 profit=3-1=2 best=4 p=6 min=1 profit=6-1=5 best=5 p=4 min=1 profit=4-1=3 best=5 → return 5
What must stay true
After processing day i, `minSoFar == min(prices[0..i])` and `best == max(prices[j] - min(prices[0..j-1]))` over j in 0..i.
Shape of the loop
minSoFar = +inf best = 0 for p in prices: best = max(best, p - minSoFar) minSoFar = min(minSoFar, p)
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Updating `minSoFar` BEFORE computing today’s profit. That lets today buy and sell on the same day, producing 0 when a real answer exists on day i.