Best Time to Buy and Sell Stock — Track a Running Minimum
Capture the lowest buying price so far and measure profit deltas in a single scan.
Problem Statement
You are given an array prices where prices[i] is the price of a stock on the i-th day. You want to maximise your profit by choosing a single day to buy and a different day in the future to sell. Return the maximum profit you can achieve, or 0 if no profit is possible.
Why This Problem Matters
- Reframes a max-profit problem as tracking two running metrics: historical minimum and best profit so far.
- Sharpens the instinct for turning "for every pair" questions into prefix or suffix aggregates.
- Prepares you for harder variants with multiple transactions by solidifying the base case.
Thought Process
Understand the constraint ordering
The buy day must occur before the sell day, so you cannot simply take the global min and max. You need a sequential strategy that respects ordering.
Track the best buy candidate incrementally
As you scan forward, maintain the lowest price seen so far. Any later day can compare against that to compute an achievable profit.
Update profit on the fly
At each day, profit = current price − minPriceSoFar. If that beats your recorded maximum, update it. Then possibly update minPriceSoFar with the current price for future iterations.
Confirm invariants
Before day i, maxProfit stores the best achievable profit using days < i. minPrice stores the best buy price seen before i. This invariant ensures correctness once the loop finishes.
Step-by-Step Reasoning
- Initialise minPrice to +Infinity and maxProfit to 0.
- For each price in prices, update minPrice = Math.min(minPrice, price).
- Compute potential = price - minPrice and update maxProfit = Math.max(maxProfit, potential).
Dry Run
Day 0 → price 7
minPrice becomes 7, profit stays 0.
Day 1 → price 1
minPrice drops to 1, no profit yet.
Day 2 → price 5
potential = 4 vs maxProfit = 0, update maxProfit to 4.
Day 3 → price 3
minPrice stays 1, profit stays 4.
Day 4 → price 6
potential = 5, update maxProfit to 5.
Day 5 → price 4
No changes; final answer 5.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Single pass over prices with constant extra storage.
Annotated Solution
public class StockTrader {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfitSoFar = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
int potential = price - minPrice;
maxProfitSoFar = Math.max(maxProfitSoFar, potential);
}
return maxProfitSoFar;
}
}The loop upholds two invariants: minPrice is the cheapest day up to i, and maxProfitSoFar is the best profit achievable so far. Each new day simply attempts to improve those values.
Common Pitfalls
- Resetting minPrice after computing profit (order matters: update minPrice before profit to avoid using the same day for both).
- Returning a negative profit when prices strictly decrease; the correct answer is 0 because you can decline to trade.
Follow-Up Questions
- How would you handle at most two transactions? (Track three states: first buy, first sell, second buy, second sell.)
- What changes if multiple transactions are allowed as long as you close positions before re-opening? (Treat it as summing positive price deltas).