Best Time to Buy and Sell Stock
Problem statement
You're given an array prices, where prices[i] is a value recorded on day i. Pick one day to "buy" at that day's value and a later day to "sell" at that day's value, so as to maximize the difference between the sell value and the buy value. If no later day is ever higher than an earlier one, the best you can do is make no move at all, for a profit of 0.
This is the same shape as scanning a metric over time — CPU price on a spot instance, or a queue depth reading — to find the largest rise from an earlier low point to a later high point, without ever looking into the future to pick your "buy" day.
Examples
Example 1
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buying at day 1 (price 1) and selling at day 4 (price 6) gives a profit of 6 - 1 = 5. No other buy-then-sell pair in the array does better.
Example 2
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: Every later day has a lower price than every earlier day, so no buy-then-sell pair makes a profit — the best choice is to make no transaction, for a profit of 0.
Hints
Approach
Optimal: Track the running minimum
Intuition
You never need to compare a day against every earlier day individually — you only ever care about the lowest price seen before it, since that's the buy day that would give the best possible profit for any given sell day. So walk through the prices once: keep track of the lowest price seen so far, and at each day, check what profit you'd get by selling today against that lowest price. That turns the brute force's full pairwise scan into one pass, which is what makes it faster.
Steps
- Set
minPriceto infinity (or the first price) andbestto 0. - For each
pricein the array, in order:- If
priceis lower thanminPrice, updateminPricetoprice(a new best day to "buy"). - Otherwise, check if
price - minPriceis bigger thanbest, and updatebestif so (a potential "sell" today).
- If
- Return
best.
Dry run
prices = [7, 1, 5, 3, 6, 4]
| price | minPrice before | action | profit if sold today | best after |
|---|---|---|---|---|
| 7 | ∞ | 7 < ∞ → minPrice = 7 | — | 0 |
| 1 | 7 | 1 < 7 → minPrice = 1 | — | 0 |
| 5 | 1 | 5 ≥ 1 → check profit | 5 - 1 = 4 | 4 |
| 3 | 1 | 3 ≥ 1 → check profit | 3 - 1 = 2 | 4 |
| 6 | 1 | 6 ≥ 1 → check profit | 6 - 1 = 5 | 5 |
| 4 | 1 | 4 ≥ 1 → check profit | 4 - 1 = 3 | 5 |
The best profit found, 5, matches the example — buying on day 1 (price 1) and selling on day 4 (price 6).
Edge cases: an array of length 1 has no day after the first to sell on, so best correctly stays 0; when prices only fall (example 2), minPrice keeps updating to each new lower value and the profit check never beats 0, so the result is 0.
Complexity
Time O(n) - a single pass over the prices, doing constant work per day.
Space O(1) - just two running values: the lowest price seen so far and the best profit seen so far.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
min_price = float("inf")
best = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > best:
best = price - min_price
return best
if __name__ == "__main__":
print(Solution().maxProfit([7, 1, 5, 3, 6, 4])) # 5
print(Solution().maxProfit([7, 6, 4, 3, 1])) # 0RecapThe whole problem in a few lines, for the night before
- Spot it: "maximize profit from one buy then one later sell" over a sequence of values
- Idea: walk through once, tracking the lowest value seen so far and the best profit against it
- Cost: O(n) time, O(1) space
- Trap: comparing every pair of days is O(n²) and too slow — only the running minimum before each day matters, not every earlier day individually
Interview follow-ups
What if you also needed to return which two days to buy and sell on, not just the profit?
Keep two extra variables — the day index of the current
minPriceand the day index of the best sell so far — updating them alongsideminPriceandbestinside the same loop. Still O(n) time and O(1) extra space, just two more variables tracked in step.The prices arrive as a live stream and you need the best profit "so far" at any moment, not just at the end?
The same running-minimum approach works incrementally: keep
minPriceandbestas persistent state, and update them each time a new price arrives, in O(1) time per price. That gives you an always-current answer without ever re-scanning the history, which is exactly what the single-pass approach already does — it just happens to also work online.
Frequently asked questions
For any given sell day, the best possible buy day is always the one with the lowest price among all the days before it — buying at a higher earlier price can never produce a better profit than buying at the lowest one. So instead of remembering every earlier price, you only need to remember the smallest one, and update it as you go.
Finding the largest rise from an earlier low point to a later high point in a single pass is the same shape as watching a time series — a spot-instance price, a queue length, a response-time metric — for the worst regression or the biggest recoverable dip, without scanning the whole history for every point. It's also a common warm-up for checking whether a candidate can recognize that a nested-loop brute force can collapse into one running-minimum pass.
That's a different, related problem (often called "Best Time to Buy and Sell Stock II"). The greedy idea there is to add up every single-day rise (prices[i+1] - prices[i] whenever it's positive), since any profitable multi-day rise can always be split into a chain of profitable one-day rises. This problem only allows a single buy and a single sell, which is why tracking one running minimum is enough.
Today's price can't be both a new record low and the best sell day against the previous low at the same time — if it's a new low, there's no profit to record yet (you'd be "selling" to yourself on the same day), and if it's not a new low, it's worth checking as a potential sell day. Structuring it as if / elif avoids doing a pointless profit check on the very day that becomes the new minimum.
