Best Time to Buy and Sell Stock
Maximise profit from one buy and one sell by tracking the cheapest price seen so far
Problem Statement
You are given an array prices where prices[i] is the price of a stock on day i.
You want to maximise profit by choosing one day to buy and a different, later day to sell. Return the maximum profit you can achieve. If no profit is possible, return 0.
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Why: buy on day 1 (price 1), sell on day 4 (price 6) → 6 - 1 = 5
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Why: prices only fall — never buy at allThe constraint that shapes everything
You must buy before you sell. 7 - 1 = 6 is not a valid answer for the first example, because price 7 happens on day 0, before price 1. Every solution has to respect this ordering.
Intuition
The brute force is to try every buy day paired with every later sell day — O(n²).
Now flip the perspective. Instead of asking "which pair should I pick?", stand on each day and ask a much simpler question:
The key insight
"If I sell today, what is the best I could have done?"
The answer is: today's price minus the cheapest price that ever occurred before today. You do not need to remember every past price — only the minimum of them.
That single remembered value collapses the problem from O(n²) to O(n). Walking left to right, you already have all the past prices behind you, so keeping a running minimum is free.
Real-world analogy
Imagine watching prices scroll by on a screen. You keep a sticky note with one number on it: the lowest price I have seen so far. Each new price, you do two things — check what you'd earn selling now against your sticky note, and update the note if the new price is lower. You never need a full history.
Approach
Track two numbers
min_price — the cheapest price seen so far (start at the first price, or infinity).
max_profit — the best profit found so far (start at 0, since doing nothing is always allowed).
For each price, first try selling
profit = price - min_price. If it beats max_profit, keep it.
Doing this before updating min_price guarantees the buy day is strictly earlier than the sell day.
Then update the minimum
If price < min_price, this becomes the new best day to have bought.
Return max_profit
If every price fell, no profit ever beat 0, so 0 is returned — meaning "don't trade".
Watch it run
Solution
def max_profit(prices: list[int]) -> int:
"""Maximum profit from a single buy followed by a later sell."""
if not prices:
return 0
min_price = prices[0]
best = 0
for price in prices[1:]:
# Try selling today against the cheapest earlier day.
best = max(best, price - min_price)
# Then consider today as a future buy day.
min_price = min(min_price, price)
return bestOrder matters
If you updated min_price before computing the profit, then on a day that sets a new minimum you would compute price - price = 0 — harmless here, but the habit breaks in similar problems. Keep the rule: sell against the past, then update the past.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — a single pass over the prices; each day does two constant-time comparisons.
- Space — only two numbers are stored regardless of how many days there are.
Edge Cases
Related Problems
- Maximum Average Subarray I — another single-pass running statistic
- Climbing Stairs — the same "collapse the DP table into variables" trick
- Jump Game — greedy decisions made in one left-to-right pass