What it teaches: Replace an O(n²) look-back with one variable (the cheapest price so far): the purest example of running state.
Practise it on judges as “Best Time to Buy and Sell Stock”.
The problem
prices[i] is a stock's price on day i. You may buy once and sell once later. Return the maximum profit you can make, or 0 if no profit is possible.
Example 1
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Buy on day 1 (price 1) and sell on day 4 (price 6).
Example 2
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Prices only fall, so don't trade.
Constraints
1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Pattern clues in the wording
→ Buy before sell: a pair (i, j) with i < j
→ Maximise a difference with a past value
→ n up to 10⁵ rules out checking all pairs
These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, best = 0;
return best;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
For each buy day i and each later sell day j, compute prices[j] - prices[i] and keep the maximum.
Approach 1
class Solution {
public int maxProfit(int[] prices) {
int best = 0;
for (int i = 0; i < prices.length; i++)
for (int j = i + 1; j < prices.length; j++)
best = Math.max(best, prices[j] - prices[i]);
return best;
}
}
Verdict: About 5 × 10⁹ pairs for n = 10⁵: too slow. The repeated work is re-finding the cheapest earlier day for every j.
2
Optimal: track the cheapest price so far
Time O(n) Space O(1)
Walk the days once. Keep minPrice, the cheapest price seen before today. Selling today earns price - minPrice; keep the best of those. Then update minPrice with today's price.
▶ Dry run: Cheapest so far, best profit so farprices = [7, 1, 5, 3, 6, 4]
7
0
↑day
1
1
5
2
3
3
6
4
4
5
State(vars)
minPrice = 7best = 0
Step 1/6Day 0: nothing to sell yet. Cheapest so far is 7.
Approach 2
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, best = 0;
for (int price : prices) {
best = Math.max(best, price - minPrice); // sell today
minPrice = Math.min(minPrice, price); // or remember today as a cheaper buy
}
return best;
}
}
Verdict: Each day is looked at once and needs only the cheapest earlier price. This is the answer.
Before you submit
Edge cases and common mistakes
Test these inputs
One day → 0
Strictly falling prices → 0
All prices equal → 0
Cheapest day is the last day
Mistakes people make
Using the overall minimum and maximum (the maximum might come before the minimum).
Returning a negative profit instead of 0.
With minPrice = Integer.MAX_VALUE, computing price - minPrice is a large negative number, which is fine; but if you wrote minPrice - price it would overflow.
Interview
Follow-up questions
What if you can buy and sell many times (one share at a time)?