Best Time to Buy and Sell Stock
Given a stock's price for each day, find the biggest profit from buying once and selling once later.
- Track the best so far in one pass
- Running minimum
Before this, know: Arrays and loops, Min and max of two numbers
You get a list prices, where prices[i] is the price of one share of a stock
on day i. You may buy once and then sell once on a later day. What is
the biggest profit you can make? Profit = sell price − buy price.
If no trade makes money, the answer is 0 (you just don’t trade).
Example: prices = [7, 1, 5, 3, 6, 4].
The rules that matter:
- You must buy before you sell. Buying at 1 on day 1 and “selling” at 7 on day 0 would be time travel.
- Only one buy and one sell.
- If prices only fall, return 0.
So for each day we need two things: today’s price, and the cheapest price on any day before today. Today’s best possible profit is their difference.
Pause and think
No. The answer stays 2 (buy at 2, sell at 4). The new low of 1 comes on the last day, so there’s no later day to sell on. A new cheapest price only helps the days that come after it. That’s why we keep a separate “best so far” instead of recomputing it from the latest low.
Try every buy day, and for each one every later sell day. Keep the biggest difference.
Brute force: every buy and sell pair
prices = [2, 4, 1]
- 20
- 41
- 12
- buy price
- —
- profit today
- —
- best
- 0
- Buy day
- Sell day
- Best trade
Try every buy day, and for each one every later sell day. Keep the biggest profit.
Which line is running?
function maxProfit(prices) { let best = 0;Running now: for (let buy = 0; buy < prices.length; buy++) { for (let sell = buy + 1; sell < prices.length; sell++) { best = Math.max(best, prices[sell] - prices[buy]); } } return best;}Brute force
function maxProfit(prices) { let best = 0; for (let buy = 0; buy < prices.length; buy++) { for (let sell = buy + 1; sell < prices.length; sell++) { best = Math.max(best, prices[sell] - prices[buy]); } } return best;}def max_profit(prices): best = 0 for buy in range(len(prices)): for sell in range(buy + 1, len(prices)): best = max(best, prices[sell] - prices[buy]) return bestWith 6 days there are 5 + 4 + 3 + 2 + 1 = 15 pairs. LeetCode allows 100,000 days: about 5 billion pairs. The work grows like n × n, O(n²). And most of that work is wasted: for each sell day, only one buy day matters, the cheapest one before it.
You can also see this as two pointers: a buy pointer that stays on the
cheapest day so far, and a sell pointer that walks forward one day at a time.
The buy pointer only ever jumps forward, to a new low.
Pattern
Track the best so far in one pass
Use it when: the answer for each position depends only on a summary of what came before it (the minimum, maximum or sum so far).
Signal words
- “buy then sell later”
- “maximum difference”
- “later element minus earlier element”
- “single pass”
- “max profit”
- Set
minPriceto infinity (bigger than any price, so the first day always beats it) andbestto 0. - Go through the prices one day at a time.
- If today’s price is lower than
minPrice, this is the new cheapest day to buy. Remember it. - Otherwise, work out today’s profit,
price − minPrice, and keep it if it beatsbest. - After the last day, return
best.
On the chart, the blue dot is the cheapest day so far (“buy”), the amber dot is today (“sell?”), and the green line is the best trade so far. Faded dots are future days the algorithm hasn’t seen yet: it never looks ahead.
One pass: cheapest price so far
prices = [7, 1, 5, 3, 6, 4]
- 70
- 11
- 52
- 33
- 64
- 45
- minPrice
- ∞
- profit today
- —
- best
- 0
- Cheapest day so far (buy)
- New cheapest day
- Today (sell?)
- Future: not seen yet
- Best trade
Walk through the days once. We remember two things: the cheapest price so far (where we'd buy) and the best profit so far. Before day 0, the cheapest price is "infinity" and the best profit is 0.
Which line is running?
function maxProfit(prices) {Running now: let minPrice = Infinity; // cheapest price seen so far let best = 0; // best profit seen so far for (const price of prices) { if (price < minPrice) { minPrice = price; // a new cheapest day to buy } else { best = Math.max(best, price - minPrice); // what if we sell today? } } return best;}Try low comes last [2, 4, 1]: the buy pointer jumps to day 2, but the best
trade stays at +2. And always falling: every day is a new low, so we never
sell and the answer is 0.
One pass with the cheapest price so far
function maxProfit(prices) { let minPrice = Infinity; // cheapest price seen so far let best = 0; // best profit seen so far for (const price of prices) { if (price < minPrice) { minPrice = price; // a new cheapest day to buy } else { best = Math.max(best, price - minPrice); // what if we sell today? } } return best;}def max_profit(prices): min_price = float("inf") # cheapest price seen so far best = 0 # best profit seen so far for price in prices: if price < min_price: min_price = price # a new cheapest day to buy else: best = max(best, price - min_price) # what if we sell today? return bestOn LeetCode it’s var maxProfit = function(prices) in JavaScript, and
def maxProfit(self, prices) inside class Solution in Python. Line numbers are
the same in both languages until the end.
- Line 2:
minPricestarts at infinity (Infinityin JavaScript,float("inf")in Python), a value bigger than every real price, so the first day’s price always replaces it. - Line 3:
beststarts at 0, which is also the answer if we never trade. - Line 4: look at each day’s price in order.
for … of(JS) andfor … in(Python) hand us the values one by one. - Lines 5–6: a new low. Selling today would earn nothing (or lose money), so just remember it as the best day to buy from now on.
- Lines 7–8: not a new low, so selling today makes
price − minPrice(zero or more). If it beatsbest, keep it. - Line 11 (JS) / line 9 (Python): the best profit after looking at every day.
prices = [7, 1, 5, 3, 6, 4]:
| day | price | price < minPrice? | minPrice after | profit if sold today | best after |
|---|---|---|---|---|---|
| 0 | 7 | yes (< ∞) | 7 | — | 0 |
| 1 | 1 | yes | 1 | — | 0 |
| 2 | 5 | no | 1 | 5 − 1 = 4 | 4 |
| 3 | 3 | no | 1 | 3 − 1 = 2 | 4 |
| 4 | 6 | no | 1 | 6 − 1 = 5 | 5 |
| 5 | 4 | no | 1 | 4 − 1 = 3 | 5 |
The day 4 row is where the answer appears. Notice minPrice settles at 1 on day 1 and
every later day measures itself against it.
Brute force
Time
O(n²)
Every buy day paired with every later sell day: about n × n ÷ 2 pairs.
Space
O(1)
Just the loop counters and best.
One pass
Time
O(n)
We look at each day exactly once. 100,000 days ≈ 100,000 steps.
Space
O(1)
Only two numbers, minPrice and best, however many days there are.
What to say out loud:
- “Brute force tries every buy-sell pair: O(n²).”
- “For any sell day, the best buy day is just the cheapest day before it.”
- “So one pass, keeping the minimum so far and the best profit so far: O(n) time, O(1) space.”
- Mention the falling-prices case and why the answer is 0.
Likely follow-up questions:
- “What if you can buy and sell many times?” That’s Best Time to Buy and Sell Stock II: add up every price rise from one day to the next.
- “What if you also need the days?” Store the index of the minimum and the best pair alongside the values (the visualizer does exactly that).
- “Is this a sliding window?” You can see it that way: the window runs from the cheapest day to today, and its left edge jumps forward when a new low appears.
Related problems:
- Longest Substring Without Repeating Characters: another single pass where the left edge jumps forward.
- Container With Most Water: also “best over all pairs”, solved without checking every pair.
- The track the best so far pattern in the week overview.