Best Time to Buy and Sell Stock
Prompt
We've got a day-by-day price series for an asset and want the best single buy-then-sell trade. Given the prices in order, what's the maximum profit from one buy followed by one later sell?
How this round runs
I haven't told you what happens if prices only fall, or whether same-day trades count — clarify before coding, and expect me to loosen a constraint once you have the single-trade version working.
Model answer
Clarify first: must the buy strictly precede the sell, or can it be the same day? If every price drops, do we return 0 (no trade) or a negative number? Is the series ever empty?
Brute force checks every buy/sell pair — O(n^2) time, O(1) space. The
insight that kills the inner loop: for any sell day, the best buy is just the
cheapest price seen before it. So track the running minimum and the best profit
in a single pass — O(n) time, O(1) space.
function maxProfit(prices) {
let minSoFar = Infinity;
let best = 0; // 0 means "don't trade" if prices only fall
for (const price of prices) {
minSoFar = Math.min(minSoFar, price);
best = Math.max(best, price - minSoFar);
}
return best;
}
Order matters: update minSoFar before computing the profit, so a new low can't
be "sold into" on the same day — the min always reflects an earlier day.
Dry-run on [7, 1, 5, 3, 6, 4]: min walks 7 then 1; profits at each step are 0,
0, 4, 2, 5, 3; best is 5 (buy at 1, sell at 6).
- Asked about the no-profit case and whether buy must precede sell
- Named the brute force, then the running-minimum single pass
- Stated O(n^2) -> O(n) time and O(1) space, before and after
- Dry-ran the min and profit updates across the series
- Now allow unlimited transactions → sum every upward step (buy-low/sell-high on each rise)
- Add a one-day cooldown after each sell → small DP over hold / sold / rest states