Best Time to Buy and Sell Stock: The Running-Minimum Pattern
Solve Best Time to Buy and Sell Stock in one pass by tracking the lowest price so far — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You're handed a list of daily stock prices and told to make one trade: buy on one day, sell on a later day, and walk away with the biggest possible profit. It sounds like it needs you to compare every buy day against every sell day — a nested-loop nightmare. It doesn't.
The whole problem collapses into a single scan once you notice one thing: on any given day, the only buy price that matters is the cheapest price you've seen so far. Everything else is noise.
That reframe — carry a running minimum, measure profit against it — is a pattern you'll reuse in dozens of array problems. Learn it here on the cleanest possible example.
The problem
Given an array prices where prices[i] is the price of a stock on day i, find the maximum profit from buying on one day and selling on a later day. You must buy before you sell. If no profit is possible, return 0.
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5 // buy on day 1 at 1, sell on day 4 at 6 → 6 - 1 = 5Two constraints shape the solution:
- The sell day must come after the buy day — you can't sell before you own.
- You make at most one transaction. Not zero-or-more trades, just one buy and one sell.
Note that buying at the global minimum (1 on day 1) and selling at the global maximum (7 on day 0) is illegal here — the max comes before the min. Order matters, and that's the trap the running minimum is built to handle.
The brute force baseline
The literal reading of the problem: try every buy day, pair it with every later sell day, keep the best difference.
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;
}This is correct, and it's slow. For each buy day it rescans the entire tail of the array looking for the best sell price — an O(n) scan repeated n times, giving O(n²) total. On a 10⁵-day price history that's roughly five billion subtractions. The interviewer wants you to name this baseline in one sentence and then delete the inner loop.
The key insight
Walk left to right and ask a different question at each day: "If I sell today, what's the most I could make?"
To answer that, you only need one number — the lowest price at any day before today. Selling today at prices[i] against the cheapest earlier price gives your best possible profit for a sale on day i:
profit if selling today = prices[i] - (minimum price seen so far)So carry two running values as you scan:
minPrice— the smallest price encountered up to now (your best buy day so far).profit— the largest sell-today profit seen across all days.
Because minPrice only ever looks at earlier days, the buy-before-sell rule is enforced for free. The inner loop disappears: one pass, constant work per day. This is the running minimum + max profit pattern.
The optimal solution
This mirrors the exact algorithm the Best Time to Buy and Sell Stock visualizer steps through:
var maxProfit = function (prices) {
let minPrice = Infinity;
let profit = 0;
for (let i = 0; i < prices.length; i += 1) {
if (prices[i] < minPrice) {
minPrice = prices[i];
}
const currentProfit = prices[i] - minPrice;
if (currentProfit > profit) {
profit = currentProfit;
}
}
return profit;
};The order inside the loop is what makes it correct. First, update minPrice if today is cheaper — this potentially lowers your best buy price. Then compute currentProfit against that possibly-updated minimum.
Updating the minimum first is safe: if today is the cheapest day yet, currentProfit becomes prices[i] - prices[i] = 0, which never beats a positive profit. You never accidentally sell on the same day you set a new low, because a zero profit can't win. Starting minPrice at Infinity means the very first day always becomes the initial minimum with a clean zero profit.
Walkthrough
Tracing prices = [7, 1, 5, 3, 6, 4], day by day:
| i | prices[i] | minPrice before | minPrice after | currentProfit | profit |
|---|---|---|---|---|---|
| 0 | 7 | ∞ | 7 | 7 − 7 = 0 | 0 |
| 1 | 1 | 7 | 1 | 1 − 1 = 0 | 0 |
| 2 | 5 | 1 | 1 | 5 − 1 = 4 | 4 |
| 3 | 3 | 1 | 1 | 3 − 1 = 2 | 4 |
| 4 | 6 | 1 | 1 | 6 − 1 = 5 | 5 |
| 5 | 4 | 1 | 1 | 4 − 1 = 3 | 5 |
Day 1 sets the low at 1 and stays the buy candidate for the rest of the scan. Day 2 books a profit of 4. Day 4 tops it with 5 — sell at 6 against the 1 low. Day 5's 4 yields only 3, so profit holds. The loop ends and returns 5, matching the buy-day-1, sell-day-4 answer.
Notice the algorithm never explicitly "commits" to a buy. It just keeps the cheapest price around and lets each day propose a sale against it — the best proposal wins.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | every buy day rescans the entire tail for a sell price |
| Running minimum | O(n) | O(1) | one pass; two scalars (minPrice, profit) updated per day |
The optimal version touches each price exactly once and stores only two numbers regardless of input size — constant extra space, linear time. You can't do better than one pass here, since you must at least read every price to know the answer.
Common mistakes
- Computing max minus min directly.
Math.max(prices) - Math.min(prices)ignores order and returns profit for a sell that might happen before the buy. On[7, 1, 5, 3, 6, 4]it gives7 - 1 = 6, which is illegal. - Initializing
profitto a negative number. Profit can't be negative — you're never forced to trade. Start it at0so a purely descending array like[7, 6, 4, 3, 1]correctly returns0. - Updating profit before the minimum. If you compute
currentProfitagainst the old minimum and only then lowerminPrice, you're one step behind on the very day a new low appears. Update the minimum first. - Tracking a "buy index" and mutating it mid-loop. You don't need indices at all for the profit answer — just the running minimum value. Extra index bookkeeping is where off-by-one bugs creep in.
Where this pattern shows up next
The running-scalar, single-pass idea generalizes across array problems where each element's answer depends only on a summary of what came before:
- Remove Duplicates from Sorted Array — a one-pass scan with a running write pointer instead of a running minimum.
- Remove Element — the same in-place overwrite technique, filtering as you go.
- Reverse String — two pointers converging in a single linear pass.
- Merge Sorted Array — a backward one-pass merge that reuses a running index.
You can also step through the visualizer to watch minPrice drop and the profit gauge climb, one day at a time.
FAQ
Why can't I just subtract the minimum price from the maximum price?
Because the maximum might occur before the minimum, and you can't sell before you buy. In [7, 1, 5, 3, 6, 4] the highest price 7 is on day 0 while the lowest 1 is on day 1, so max - min = 6 describes an impossible trade. The running-minimum scan only ever compares today's price against lows from earlier days, which enforces the buy-before-sell rule automatically and returns the legal answer of 5.
What is the time and space complexity of the optimal solution?
O(n) time and O(1) space. The array is scanned exactly once, doing a constant amount of work per day — one comparison to maybe lower minPrice, one subtraction, and one comparison to maybe raise profit. Only two scalar variables are stored no matter how long the price history is, so extra memory stays constant. The nested-loop brute force is O(n²) time by contrast.
What should the function return when no profit is possible?
Zero. If prices only fall — like [7, 6, 4, 3, 1] — no later day is ever higher than an earlier low, so currentProfit stays at or below 0 on every iteration and never overwrites the initial profit = 0. Returning 0 reflects the correct choice of simply not trading, which the problem allows.
How is this different from Best Time to Buy and Sell Stock II?
This problem permits one transaction — a single buy and a single sell. The II variant lets you trade as many times as you want, buying and selling repeatedly. That changes the strategy entirely: II becomes a greedy sum of every upward step (add prices[i] - prices[i-1] whenever it's positive), whereas this version tracks a single running minimum to find one best trade.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.