FAANGPrep Sprint
Best Time to Buy and Sell Stock
Find the best profit from one buy followed by one later sell.
Examples
Buy on day 1 at 1 and sell on day 4 at 6.
The price only falls, so no transaction makes money.
The cheapest day, 1, comes too late — the best sale is still 3 to 8.
Problem Understanding
prices[i] is a stock's price on day i. You may make one trade: buy on a single day, then sell on a later day.
Return the largest profit that one trade can earn, or 0 if every possible trade would lose money.
Strategy
Walk the prices once, carrying two numbers: the cheapest price so far, the only buy price worth considering for a sale today, and the best profit so far, the largest price - min_price seen on any day.
Start with
min_price = infinityandmax_profit = 0.For each price, lower the minimum:
min_price = min(min_price, price).Then raise the best:
max_profit = max(max_profit, price - min_price).Return
max_profit.
Interactive Visualization
ONE COLUMN PER DAY · MIN = CHEAPEST SO FAR · SELL = PRICE − MIN · OUTLINED = THE BUY DAY THIS SALE IS MEASURED AGAINST
NOTHING SEEN YET
0
1
2
3
4
5
price
min
sell
cheapest so far
—
best profit
0
Answer
—
every day
best = the larger of best and price − min
Nothing has been seen yet: the cheapest price is infinite and the best profit is 0
Next
Day 0: the price is 7
prices
Legend & Complexity
The day being processed
The buy day a sale today is measured against
A dash: that day has not been reached
Time
O(n)
Space
O(1)
Every pair
O(n²)
The lesson's own dry-run table, filling in. Each column is a day: its price, the cheapest price up to that day, and what selling that day would make. The buy day a sale is measured against is outlined in the price row, so every profit is visibly this cell minus that cell.
Try Late low: the cheapest day comes after the best sale, and the answer is unaffected.
Dry Run
prices = [7, 1, 5, 3, 6, 4], days counted from 0 as in the figure:
| Day | Price | Min price so far | Sell today (price - min) | Max profit |
|---|---|---|---|---|
| 0 | 7 | 7 | 7-7=0 | 0 |
| 1 | 1 | 1 | 1-1=0 | 0 |
| 2 | 5 | 1 | 5-1=4 | 4 |
| 3 | 3 | 1 | 3-1=2 | 4 |
| 4 | 6 | 1 | 6-1=5 | 5 |
| 5 | 4 | 1 | 4-1=3 | 5 |
Buy on day 1 at 1, sell on day 4 at 6 — return 5.
Edge Cases & Common Mistakes
Watch out for these:
A falling market answers 0. If no day is cheaper than a later one, return 0 — never a negative profit.
The cheapest day is not always part of the answer. In [3, 8, 1, 4] the minimum, 1, arrives after the best sale. Tracking the best profit as you go, not just the minimum, is what handles it.
You cannot sell before you buy. Updating the minimum before computing today’s sale makes a same-day trade worth 0, so it can never be counted as profit.
Solution
One pass, two running values — the lines light up as the figure above steps.
Best Time to Buy and Sell Stock Code
1var maxProfit = function(prices) {2 let minPrice = Infinity;3 let maxProfit = 0;4 for (const price of prices) {5 minPrice = Math.min(minPrice, price);6 maxProfit = Math.max(maxProfit, price - minPrice);7 }8 return maxProfit;9};