Best Time to Buy and Sell Stock looks like it needs to compare every pair of days, but a single left-to-right pass does it. The trick is to carry just two running values as you scan — the cheapest price seen so far, and the best profit you could have made.
Problem. You are given an array prices where prices[i] is the price of a stock on day i. You
may buy on one day and sell on a later day. Return the maximum profit you can make. If no profit
is possible, return 0.
Example: prices = [7, 1, 5, 3, 6, 4] → answer 5 (buy on day 1 at price 1, sell on day 4 at price 6, profit 6 − 1 = 5).
The slow way first
The obvious idea: try every pair of days. For each buy day, look at every later sell day and check the profit. That works, but it is O(n²) — for a long price history it is far too slow.
The question to ask: while I stand on a possible sell day, what do I wish I already knew? I wish I knew the lowest price before today. If I always know the cheapest day so far, then today's best profit is just today − cheapest. I can track that cheapest price as I go.
The idea: track the minimum so far
Walk the array once, left to right. Keep two values:
min_price— the lowest price seen so far (the best day to have bought).best— the largest profit found so far.
For each price: if it is a new low, update min_price (we would rather have bought here). Otherwise, pretend we sell today: the profit is price − min_price, and we keep it if it beats best.
Because min_price is always the cheapest day we have already seen, we never sell before we buy. The lowest price always comes from an earlier day.
Walk through it
Step through the animation. The pointer price scans left to right. The two labels show min price and best profit updating. The price drops to 1 early, so every later day measures its profit against 1. The best profit, 5, comes from selling on the day the price is 6.
Pseudocode
min_price = infinity # cheapest day seen so far
best = 0 # best profit so far
for each price in prices:
if price < min_price:
min_price = price # found a cheaper day to buy
else:
profit = price - min_price
best = max(best, profit) # could we sell higher today?
return bestThe whole solution is one loop with two simple updates and no inner loop.
The Python solution
def max_profit(prices):
min_price = float("inf")
best = 0
for price in prices:
if price < min_price:
min_price = price
else:
best = max(best, price - min_price)
return bestmin_pricestarts at infinity so the very first price always becomes the new low.beststarts at0— that is the answer if prices only ever fall.- Line 5 asks: is today a new cheapest buy day? If yes, line 6 records it.
- Otherwise (line 7), line 8 tries selling today:
price - min_priceis the profit, andmaxkeeps the better of that and the previous best. - We return
bestafter one pass — no second loop needed.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every pair) | O(n²) (slow) | two nested loops over days |
| One pass (this solution) | O(n) (moderate) | scan once, O(1) work per day |
O(1) (fast)This is even better than the hash-map trade: we only keep two numbers, so the extra space is O(1). The idea — carry a running minimum and a running answer in one sweep — is one of the most common patterns in array problems.
When this pattern shows up
Whenever a problem asks for the best result "so far" while scanning — max profit, longest run, running maximum, smallest seen — reach for one pass with a couple of running variables. You rarely need to compare every pair; tracking the right summary as you go collapses O(n²) into O(n).
You can only sell after you buy. That is why we update min_price from earlier days only and compute
profit as price − min_price — never the other way around. If you allowed selling before buying you could
report an impossible "profit."
Practice
For prices = [7, 1, 5, 3, 6, 4], when price reaches 6, what is min_price and what profit does this day offer?
1. What two values does the one-pass solution track as it scans?
2. Why is it safe to compute profit as price − min_price?
3. What does max_profit return if the prices only ever fall, like [7, 6, 4, 3, 1]?
4. What is the extra space used by the one-pass solution?