#121
Best Time to Buy and Sell Stock
Easy Running minimum
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
prices[i] is a stock's price on day i. Buy on one day and sell on a later day for the biggest profit; return 0 if no profit is possible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: pick a buy day and a later sell day to make the most money.
Why this works: if you sell today, the best buy day is the cheapest day so far. Keep that minimum as you scan.
Example: [7, 1, 5, 3, 6, 4]
day 1: min 1day 2: sell at 5 → profit 4day 4: sell at 6 → profit 5 (best)answer 5
✦Hints open one at a time
For each selling day, the best buying day is the cheapest day before it.
Track the minimum price seen so far as you scan.
↗Approach
One pass: keep the lowest price so far and the best profit of selling today. No need to look back at every earlier day.
</>Solution (Java)
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, best = 0;
for (int p : prices) {
minPrice = Math.min(minPrice, p); // cheapest day so far
best = Math.max(best, p - minPrice); // sell today
}
return best;
}
}!Common mistake
Taking max − min of the whole array; the max might come before the min.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Arrays
