Best Time to Buy and Sell Stock
How to find the single most profitable buy-then-sell pair in one pass, without checking every pair of days.
The job
You are given a stock's price on each of several days. Choose one day to buy and a LATER day to sell so the profit is as large as possible.
The obvious way
Try every pair of a buy day and a later sell day, and keep the best difference.For 6 days that is on the order of 15 pairs.
The idea
Walk the prices once, remembering the lowest price seen SO FAR. At every day, the best sell you could make right now is today's price minus that running minimum — no need to revisit earlier days to check.
Think of it like this. Watching gas prices all month, remembering the cheapest day so far. Every time you pass a station, you instantly know your best possible savings if you had filled up on the cheapest day and are paying today's price — no need to replay the whole month to work it out.
One buy, one later sell — maximize the gap
6 days of prices. Buy on one day, sell on a LATER day, and maximize the profit.
def max_profit(prices):
min_price = prices[0]
best = 0
for price in prices[1:]:
best = max(best, price - min_price)
min_price = min(min_price, price)
return bestThis run
Buy on day 1 at 1, sell on day 4 at 6, for a profit of 5.
The names you just watched
min_price
The lowest price seen up to and including today. It only ever moves down, and it is the only past information the algorithm needs to keep.
One direction in time
Selling must happen on a LATER day than buying, so the running minimum is always built from days strictly before the one being priced right now.
Why this beats checking every pair
Every day answers "what if I sold today?" using one number, not a search back through history — so the whole scan is one pass instead of a pair for every (buy, sell) combination.
How to spot this shape
The tell: You need the best gap between an earlier and a later value in a sequence, and a single running extreme (min or max) is enough to evaluate every later position in O(1).
Reach for it when
- One value must come strictly before another in the sequence (buy before sell).
- The answer is a difference or ratio between two positions, one earlier and one later.
- A brute-force answer checks every (earlier, later) pair.
- Only the best earlier value matters — ties or near-best earlier values change nothing.
Not this when
- You can hold multiple overlapping positions at once — that needs a different accounting.
- The order does not matter (any two elements can pair) — that is closer to two-pointers or sorting.
- More than one buy/sell round is allowed — that needs extra running state per round.
- A transaction cost or cooldown changes which days are even eligible — the running minimum alone is no longer enough.
Practice
6 problemsThe lesson, exactly. One pass, one running minimum, one running best-gap.
Unlimited trades changes the greedy: take every single up-day, since any rise can be captured as its own tiny trade.
Track four running numbers instead of two — best profit after 1st buy, 1st sell, 2nd buy, 2nd sell — updated in that order each day.
Generalize III to k trades: 2k running numbers instead of 4, same day-by-day update order.
A state machine (held / sold-today / resting) replacing the single running minimum — the cooldown forces a one-day gap after every sell.
Same II-style unlimited trades, but subtract the fee at sell time — which changes which up-days are even worth taking.