The problem
You get a list of a stock’s price on each day. Choose one day to buy and a later day to sell to make the most profit. If no profit is possible, return 0.
Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 (buy at 1, sell at 6)
Picture it
Picture a price chart with one bar per day. We walk forward through time with a finger marking the cheapest day so far (the dip). Each new day we ask: “if I had bought at that dip and sold today, how much would I make?” We keep the best answer. If today is even cheaper, the dip moves here.
How to recognise it
- You choose two moments, an earlier one and a later one, and the score is later minus earlier.
- For each possible later day, only one earlier day matters: the cheapest one so far.
- "The best so far" can be carried along in one variable as you walk the list, like the left edge of a window that only moves to a cheaper day.
- Up to 10^5 prices, so checking every pair of days is too slow.
Start with brute force
Try every buy day i and every later sell day j, and keep the largest profit. Start at 0, since you may choose not to trade.
def max_profit_brute(prices):
best = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
best = max(best, prices[j] - prices[i])
return best
There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). With n = 10^5 that is about 5 × 10^9 pairs, far too slow.
From brute force to the idea
- Fix the sell day instead. For a sell day j, the best buy day is the cheapest day before j. The other earlier days cannot do better.
- Find the waste. The brute force recomputes "the cheapest earlier day" for every j by rescanning, but it only changes when a new low price appears.
- Carry the minimum. Keep
cheapest, the lowest price seen so far. For each new price p, the best profit from selling today isp - cheapest. - Then update. After checking, set
cheapest = min(cheapest, p). Checking first means you never sell on the day you buy; here that would only give 0, so the order is safe either way. - Start at 0. If prices only fall, every
p - cheapestis negative or zero, andbeststays 0, which is what the problem asks for.
This is the key idea: for each day, the best trade ending today buys at the cheapest price seen so far.
The key idea
Track the minimum price so far and the best (today − minimum). One pass, O(n).
Python solution
def max_profit(prices):
if not prices: return 0 # no days
cheapest, best = prices[0], 0
for p in prices[1:]: # sell or rebuy?
best = max(best, p - cheapest)
cheapest = min(cheapest, p)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every buy and sell pair | O(1): one best value |
| Running minimum (shown code) | O(n): one pass with two comparisons per day | O(1) extra besides prices[1:], which copies the list (O(n)); looping over indices avoids that copy |
Edge cases
- Empty list: the guard
if not prices: return 0handles it. LeetCode guarantees at least one price. - One day: returns 0; there is no later day to sell on.
- Falling prices (
[7, 6, 4, 3, 1]): returns 0, no trade. - Flat prices (
[3, 3, 3]): returns 0. - New low after the best trade (
[2, 4, 1]): returns 2. The later low of 1 has no higher day after it, so the earlier trade stands. - New low that leads to a better trade (
[2, 4, 1, 7]): returns 6, buying at 1.
Common mistakes
- Returning
max(prices) - min(prices). The maximum may come before the minimum:[5, 1]gives 4, but you cannot sell before you buy, so the answer is 0. - Starting
bestat-infor atprices[1] - prices[0], which returns a loss instead of 0 when prices only fall. - Resetting
bestwhenever a new low appears, which throws away a good trade made earlier. - Starting
cheapestat 0, which makes every price look like profit.
Return the largest nums[j] - nums[i] with i < j and nums[i] < nums[j], or −1 if no such pair exists. For [7, 1, 5, 4] the answer is 4; for [9, 4, 3, 2] and [5, 5] it is −1. Describe your approach, then write it if you like.
Compare with our answer
Same running minimum. The only changes are the starting value (−1 means "nothing found yet") and the condition: a day only counts if it is strictly above the minimum, so equal values never produce a 0.
def maximum_difference(nums):
best, low = -1, nums[0]
for x in nums[1:]:
if x > low:
best = max(best, x - low)
low = min(low, x)
return best
Time O(n), space O(1) apart from the slice. It assumes at least two numbers.
A strong answer mentions: reusing the running minimum, the strict > so that equal values are rejected, and −1 as the "no pair" start.
1. You must maximise values[i] + values[j] + i - j over pairs i < j. Which approach fits best?
The score splits into a part for i and a part for j, so for each j you only need the best earlier values[i] + i, just like the cheapest earlier price. Sorting loses the positions, and the pair check is O(n²).
2. Why does the shown code never need to look back at earlier days?
For any sell day, the best buy is the cheapest earlier day, and cheapest holds exactly that price. Prices are not sorted, and best is never reset.
3. A learner returns max(prices) - min(prices). Which input now gets a wrong answer?
In [5, 1] the highest price comes first, so the shortcut sells before buying and reports 4. In the other inputs the maximum happens to come after the minimum, so the shortcut agrees by luck.
Score 60% or more and the lesson is marked complete.