Best Time to Buy and Sell Stock
Track the cheapest price so far and the best profit against it.
Sliding Window Trace
Problem
You are given a sequence of daily stock prices. Choose one day to buy and a later day to sell, or make no transaction at all. Return the largest profit possible from that single transaction.
Examples
Input: prices = [7,1,5,3,6,4]
Output: 5
Input: prices = [7,6,4,3,1]
Output: 0
The Goal
Buy on one day and sell on a later day. Return the most you can make, or 0 if no trade makes money.
For [7, 1, 5, 3, 6, 4], buy at 1 and sell at 6 for a profit of 5. The buy has to come first, and here the 1 does come before the 6.
One trade, forward in time
A sale can only use prices you've already seen. Scan left to right and the time order takes care of itself.
Key Idea: Cheapest Price So Far
On any day, you need one fact about the past: the cheapest price so far. A more expensive buy would make less if you sold today.
So keep two numbers. min_price is the best buy so far, and best_profit is the best sale so far. Today's best sale is price - min_price.
The cheapest price so far: the best buy for a sale today.
After 7 and 1, min_price = 1.
The Algorithm
Think of it as a window. The right edge is today, the possible sale. The left edge is the cheapest day before it, the buy. A new low moves the left edge there.
min_price = float("inf")
best_profit = 0
for price in prices:
min_price = min(min_price, price)
best_profit = max(best_profit, price - min_price)
return best_profitbest_profit starts at 0, so falling prices return 0 instead of a loss.
| Approach | Time | Space | How |
|---|---|---|---|
| Try every buy/sell pair | O(n^2) | O(1) | Rechecks the same earlier prices |
| Running minimum | O(n) | O(1) | min_price stands in for every earlier buy |
Walkthrough
Run it on [7, 1, 5, 3, 6, 4].
Day 0 buys at 7. Day 1 finds a cheaper buy at 1. After that, every day is a possible sale against 1: selling at 5 makes 4, at 3 makes 2, at 6 makes 5, and at 4 makes 3.
The best is 5: buy on day 1, sell on day 4. A new low later on could only help sales after it.
Checkpoint · predict the next step
Step 4 of 8 on the stage: Day 2: sell at 5 after buying at 1: 5 − 1 = 4, the best so far.
window [1, 5] (buy 1, sell 2) · min_price 1 · profit 4 · best_profit 4
Pitfalls
- Checking every pair of days works, but it's
O(n²). - Don't sort the prices. The order is what makes a trade legal.
- Don't buy at the lowest price overall if it comes after the sale.
- If prices only fall, the answer is 0. For
[7, 6, 4, 3, 1], no trade beats doing nothing.
Why does [7, 6, 4, 3, 1] return 0?
Complexity
One pass over the prices, with constant work per day: O(n) time. You keep two numbers, so extra space is O(1).
Nothing can do better, because every price has to be read at least once.
One pass against every pair
- Scan prices onceEach day is read once.dominantO(n)
- Update min and profitConstant work per day.O(1)
- Running statemin_price and best_profit.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Optimal: every price has to be read once anyway.
In short
Sweep once, keeping the minimum price seen. At each day, the best sale is today's price minus that running minimum; keep the largest such difference. It's a one-pass sliding view of 'buy low before, sell here'.
Common mistake
Comparing every buy/sell pair (O(n²)) instead of tracking the running minimum.