Best Time to Buy and Sell Stock
Given daily prices, pick one day to buy and a later day to sell to maximize profit. Return the best profit, or 0 if no profit is possible.
Intuition
Profit on any day equals today's price minus the cheapest price seen so far. We never need to know the future — only the lowest price in the past. So sweep once, tracking the running minimum and the best profit it could produce.
Approach
Brute force, and the redundancy hiding in it
The literal reading of the problem is: try every buy day, pair it with every later sell day, and keep the largest difference — O(n²). If you watch that computation closely, you'll see it keeps re-asking the same thing: for a given sell day, the best possible profit only depends on the cheapest price that appeared before it. We're recomputing that minimum again and again.
Carry the cheapest-so-far instead of looking back
Flip the perspective: walk forward and, at each day, pretend you're selling today. The best you could have done is today's price minus the lowest price seen on any earlier day. So if we keep a running minPrice, the profit available today is just price − minPrice — no backward scan needed. The minimum is the one piece of history that actually matters, and it's a single number.
One pass, update best then min
Start minPrice at the first price and best at 0 (the do-nothing profit). For each later price: first record the profit price − minPrice against best, then lower minPrice if today is cheaper. Doing it in that order means we never sell and buy on the same day. If prices only fall, every candidate profit is negative, best stays 0, and we correctly report 'no trade.' O(n) time, O(1) space.
Solution & live demo
Edge cases
Every price − minPrice is ≤ 0, so best stays at its starting 0 — correctly reporting no profitable trade.
The loop over later prices never runs; best returns 0, since you cannot buy and sell on the same day.
minPrice starts at prices[0], so a later peak is measured against it immediately.