Best Time to Buy & Sell Stock
EasyTrack the lowest price behind you
Remember the cheapest day so far, and at each day check how much you'd make selling now; keep the best.
The idea
Walk the prices keeping the minimum seen so far as your buy day. At each day, the best profit is price − minSoFar. Keep the maximum of those.
7
1
5
3
6
4
0
1
2
3
4
5
Step 1 of 17. Brute force: try buying on every day and selling on every later day. Values: 7, 1, 5, 3, 6, 4.
1/17
Brute force
timeO(n²)spaceO(1)
Every buy/sell pair.
1for (let i = 0; i < n; i++)2 for (let j = i + 1; j < n; j++)3 best = Math.max(best, prices[j] - prices[i]);Input
- array
- [7, 1, 5, 3, 6, 4]
Memory
- buy
- —
- sell
- —
Output
- best
- —
- 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.