Greedy — Best Time to Buy and Sell Stock
↗ LeetCode: Best Time to Buy and Sell Stock · Easy · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftAppleBloombergAdobe
At most one buy + one sell. Max profit.
Example 1 — prices=[7,1,5,3,6,4] → 5Example 2 — prices=[7,6,4,3,1] → 0
Constraints — 1 ≤ n ≤ 10⁵. Brute compares every buy/sell pair in O(n²) = 10¹⁰ ops at n=10⁵ (TLE). One-pass tracking min-so-far and max profit is O(n) = 10⁵ ops = <5 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Compare every pair
O(n²). Baseline.
Approach 2 — Track running minimum (canonical)
Insight. Max profit if selling on day i = prices[i] - min(prices[0..i-1]).
java
int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, best = 0;
for (int p : prices) {
min = Math.min(min, p);
best = Math.max(best, p - min);
}
return best;
}Execution Trace
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Pairs | O(n²) | O(1) | baseline |
| Min tracking | O(n) | O(1) | canonical |
When to use which
- Single transaction → min tracking.
- Unlimited transactions → sum positive diffs (see Stock II).
- k transactions → DP (see Stock IV).
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems