Topic · GreedyEasy
Best Time to Buy and Sell Stock
Understand the problem
Given an array prices, where prices[i] is the stock price on day i.
- You may buy once and sell once afterwards.
- Return the maximum profit; if no profit is possible, return 0.
ts
prices = [7,1,5,3,6,4] → 5 // buy at price 1, sell at price 6
prices = [7,6,4,3,1] → 0 // the price only drops → don't buyKey idea: scan once and always remember the lowest price seen so far (the best day to buy up to now).
- Each day, try selling: profit = today's price − lowest price.
- This is a locally optimal, greedy choice.
Show the basic approach (slower)
Basic approach
O(n²) time, O(1) spacets
function maxProfitNaive(prices: number[]): number {
let best = 0
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
best = Math.max(best, prices[j] - prices[i]) // buy on day i, sell on day j
}
}
return best
}Why this approach is slow:
This tries every buy-sell pair of days → two nested loops, O(n²).
Remembering the lowest price so far is enough, which reduces it to a single O(n) pass.
Optimal solution
Optimal
O(n) time, O(1) spacets
function maxProfit(prices: number[]): number {
let minPrice = Infinity
let maxProfit = 0
for (const price of prices) {
if (price < minPrice) {
minPrice = price // best day to buy so far
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice // would selling today earn more?
}
}
return maxProfit
}Key insight:
One pass, two variables: the lowest price seen and the best profit.
- On each day, either update to a lower buy price or try to cash in.
- The greedy choice "buy at the lowest point so far" gives the optimal result without a dp table.
Step-by-step trace
Step through the run — click a step to see its line of code
1function maxProfit(prices: number[]): number {2 let minPrice = Infinity3 let maxProfit = 04 5 for (const price of prices) {6 if (price < minPrice) {7 minPrice = price // best day to buy so far8 } else if (price - minPrice > maxProfit) {9 maxProfit = price - minPrice // would selling today earn more?10 }11 }12 13 return maxProfit14}Edge cases to remember
Empty array or a single day → nothing to sell → 0.
Prices fall continuously [7,6,4,3,1] → no day is profitable → 0.
Prices rise continuously → profit = last price − first price.
The lowest price comes last → there's no day left to sell → the earlier low is still used.