Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock is LeetCode 121 (Easy). You get an array prices, where prices[i] is the price of one stock on day i. Return the maximum profit from a single buy and a single sell, the classic maximum profit stock one transaction question.
- You buy on one day and sell on a later day, so the sell index must be strictly greater than the buy index.
- Exactly one transaction is allowed, not a sequence of them.
- If no pair of days turns a profit, return 0: doing nothing is always permitted.
There are up to 10⁵ days, so checking every buy-sell pair is about 5 billion comparisons and too slow. One linear pass is needed.
- 1 <= prices.length <= 10⁵
- 0 <= prices[i] <= 10⁴
Intuition
Instead of asking which pair of days is best, ask a question about each day on its own: if I sell today, what is the most I can make? The buy has to be earlier, so the answer is today's price minus the cheapest price before today.
That turns the whole problem into one remembered number. Walk left to right carrying the minimum seen so far, score each day against it, and keep the largest score. Every valid sell day is tested against its own best possible buy day, so the true maximum cannot be missed.
The tell is a constraint forcing i < j together with a question about the best pair. You rarely need both indices: sweep once and carry the single best-so-far fact about everything to the left. Maximum subarray and container with most water run on the same instinct, and the harder stock variants (II, III, IV, with a fee or a cooldown) swap this one number for a small set of DP states.
Approach
Before reading on, take [7, 1, 5, 3, 6, 4] and find the best trade by hand. Then ask what single number you would have to carry while walking left to right to drop the inner loop. Aim for O(n) time and O(1) space.
Seed from the first day
Set min_price to prices[0] and best to 0. Seeding the minimum from a real price means a later peak is measured against day 0 immediately, and a one-day array simply returns 0 because the loop never runs.
Score each day, then update the minimum
For each later price p, do two things in this order:
- Score it: compute
p - min_priceand keep it if it beatsbest. That is the profit of buying at the cheapest earlier day and selling today. - Then fold it into the minimum: only after scoring does
pjoinmin_price. The other order lets a new low be its own buy price and counts a same-day trade.
Why zero is the right start
On a falling market every difference is negative and best never moves off 0, which is exactly the answer, since you are allowed not to trade. Starting from the first real difference instead would report the smallest loss.
Best Time to Buy and Sell Stock solution in Python | C++ | Java
Common pitfalls
Updating the minimum before taking the profit
for p in prices[1:]:
min_price = min(min_price, p)
best = max(best, p - min_price)for p in prices[1:]:
best = max(best, p - min_price)
min_price = min(min_price, p)If today is the new low then min_price becomes p and the profit computes as p - p = 0, which is a buy and a sell on the same day. Score today's sale against the earlier days first, then let today join the minimum.
Seeding the best profit with a real difference
best = prices[1] - prices[0]
best = 0
On [7, 6, 4, 3, 1] every trade loses money and the answer is 0, because no transaction is a legal choice. Seeding with a difference reports the least-bad loss instead.
Starting the minimum at a language MAX constant
int minPrice = INT_MAX; best = max(best, prices[i] - minPrice);
int minPrice = prices[0];
In C++ or Java prices[i] - INT_MAX underflows to a large positive number and wins the max, returning nonsense. Seed from prices[0] and start the loop at index 1.
Edge cases
[7, 6, 4, 3, 1]Every difference is negative, so best stays 0 and no trade is reported.
[5]There is no later day to sell on, the loop body never runs, and 0 is returned.
[3, 3, 3]Each difference is 0, which never beats best, so the answer is 0.
Complexity
prices, carrying the cheapest price so far and the best profit so far. No array or table is built, so the extra space is two integers.Best Time to Buy and Sell Stock FAQ
Why can't you just subtract the minimum price from the maximum price?
Because the maximum may come before the minimum. On [7, 1, 5, 3, 6, 4] that happens to work, but on [9, 1] the highest price is on day 0, and selling before you buy is not allowed. Scoring each day against the minimum behind it keeps the order correct.
How is this different from Best Time to Buy and Sell Stock II?
121 allows exactly one transaction, so the answer is the largest single rise anywhere in the array. 122 allows unlimited transactions, so the answer is the sum of every daily rise. Different questions, and the greedy for 122 is wrong here.