Best time to buy and sell stock
MediumCheapest so far, best profit so far
Problem
Return the maximum profit from a single buy-then-sell of a stock given daily prices.
Track the cheapest price so far and, at each day, see how much you'd earn selling today.
The idea
Track the minimum price seen and the best profit achievable by selling today. Since the minimum always comes from an earlier day, buying before selling is enforced automatically.
The trick
- Update the profit before the minimum, so buy and sell are never the same day.
- One transaction only; the answer is never negative.
- O(n), O(1) space.
Step 1 of 8. Track the lowest price behind you; at each day the best profit is today's price minus that minimum. Values: 7, 1, 5, 3, 6, 4. minSoFar ∞, best 0.
One pass, min + best.
1let min = Infinity, best = 0;2for (const p of prices) {3 min = Math.min(min, p);4 best = Math.max(best, p - min);5}Input
- array
- [7, 1, 5, 3, 6, 4]
Memory
- buy
- —
- day
- —
- minSoFar
- ∞
- profit
- —
Output
- best
- 0
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- prices = [7, 1, 5, 3, 6, 4]
- Output:
- 5
- Explanation:
- Buy at 1, sell at 6 → profit 5.
Example 2
- Input:
- prices = [7, 6, 4, 3, 1]
- Output:
- 0
- Explanation:
- Prices only fall, so no profit → 0.
Example 3
- Input:
- prices = [2, 4, 1]
- Output:
- 2
- Explanation:
- Buy at 2, sell at 4 → profit 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.