Best Time to Buy and Sell Stock
Maximize profit with one buy and one sell. Track the minimum so far in a single pass.
arraysgreedy
Intro
Given daily prices, you can complete at most one transaction. Return the maximum profit.
Key insight
The best sell on day i is `prices[i] - min(prices[0..i-1])`. Track the running minimum as you go.
Approach
- 1minSoFar = +infinity; best = 0.
- 2For each price p: best = max(best, p - minSoFar); then minSoFar = min(minSoFar, p).
Complexity
Time
O(n)
Space
O(1)
Code
Snippetjava
int maxProfit(int[] p) {
int minSoFar = Integer.MAX_VALUE, best = 0;
for (int x : p) {
best = Math.max(best, x - minSoFar);
minSoFar = Math.min(minSoFar, x);
}
return best;
}Pitfalls
- Updating minSoFar before computing profit — loses today's potential sell.
Variants & follow-ups
- Best Time to Buy and Sell Stock II / III / IV (LC 122 / 123 / 188)