Part 2 · Problems · Sliding window
Best Time to Buy and Sell Stock
#121 · Easy · LeetCode
prices[i] is the price on day i. Buy once, sell once later. Return the max profit, or 0.
[7,1,5,3,6,4] -> 5 (buy 1, sell 6) [7,6,4,3,1] -> 0
Ask before coding
- Must buy before selling?
- Can profit be zero?
Hint
For each day as the sell day, what's the best buy day before it?
Approach
Track the lowest price seen so far. Each day, profit if sold today = price - lowest. Keep the best.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function maxProfit(prices) {
let minSoFar = Infinity,
best = 0;
for (const p of prices) {
minSoFar = Math.min(minSoFar, p);
best = Math.max(best, p - minSoFar);
}
return best;
}Traps
- Taking global max minus global min ignores order (the min might come after the max).
Say out loud: For each sell day I just need the cheapest day before it, so I carry a running minimum.