#121 Best Time to Buy and Sell Stock
the problem
In plain words
prices[i] is a stock's price on day i. Buy on one day and sell on a later day. Return the maximum profit, or 0 if no profit is possible.
in prices = [7,1,5,3,6,4]
out 5
Buy at 1 (day 1), sell at 6 (day 4).
in prices = [7,6,4,3,1]
out 0
Prices only fall, so don't trade.
- 1 ≤ n ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternKadane / running best
If you sell today, the best buy day is simply the cheapest day before today. Keep that running minimum and you never need a second loop.
solutions
From brute force to optimal
Try every buy day with every later sell day.
- For each buy, for each sell > buy, track the max of prices[sell] − prices[buy].
All pairs of days — too slow for n = 10⁵.
One running maximum.
class Solution { public int maxProfit(int[] prices) { int best = 0; for (int buy = 0; buy < prices.length; buy++) for (int sell = buy + 1; sell < prices.length; sell++) best = Math.max(best, prices[sell] - prices[buy]); return best; }}Scan left to right, remembering the lowest price so far; each day, try selling.
- minPrice = +∞, best = 0.
- If price < minPrice, it's the new buy day.
- Otherwise best = max(best, price − minPrice).
One pass, constant work per day.
Two variables.
class Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE, best = 0; for (int price : prices) { if (price < minPrice) minPrice = price; // cheapest buy day so far else best = Math.max(best, price - minPrice); // what if we sell today? } return best; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: one transaction only, and selling must come after buying.
- Say the key sentence: "for each sell day, the best buy day is the minimum before it."
- Mention this is Kadane in disguise: the max subarray of day-to-day price differences.
traps
- Returning a negative profit when prices only fall — the answer is 0.
- Using the global minimum even when it comes after the maximum.
what they ask next
Follow-ups
Unlimited transactions (LC 122)?
Add every positive day-to-day rise: sum of max(0, prices[i] − prices[i−1]). O(n). It's the next problem in this chapter.
At most k transactions or a cooldown (LC 188, 309)?
Those need dynamic programming with buy/sell states — the DP Patterns chapter solves both as a small state machine.
before you submit
Edge cases to test
- One day → 0 (you can't buy and sell on different days).
- Prices only fall → 0, never a negative profit.
- The global minimum comes after the global maximum ([2,4,1] → 2).
practise next
Similar problems
- #122Best Time to Buy and Sell Stock IIMediumin Arrays & Strings
- #53Maximum SubarrayMediumin Arrays & Strings