Best Time to Buy and Sell Stock
Understanding the Problem
The goal is to maximize prices[j] - prices[i] over all pairs of days with i < j. The ordering requirement rules out the obvious shortcut: you cannot subtract the global minimum from the global maximum, because the minimum might come after the maximum.
In [7, 6, 4, 3, 1], the minimum is 1 and the maximum is 7, but 7 comes before 1. Buying at 7 and selling at 1 produces a loss, not a profit.
A more useful framing: for each day, what is the cheapest price on any earlier day? Selling on that day earns the current price minus that cheapest earlier price, and the answer is the maximum of these values across all days.
Key Constraints:
1 <= prices.length <= 10^5→ An O(n^2) scan of all pairs is on the order of 10^10 operations at this size and will time out. The solution needs to be O(n log n) or better.0 <= prices[i] <= 10^4→ Prices are non-negative, and the difference between any two fits comfortably in a 32-bit integer.
Approach 1: Brute Force
Intuition
Try every valid transaction. For each buy day i, check every later sell day j, compute the profit prices[j] - prices[i], and keep the maximum. Since every pair is examined, the best one cannot be missed.
Algorithm
- Initialize
maxProfitto 0 (if no profitable transaction exists, we return 0) - For each day
ifrom 0 to n-2 (potential buy day): - For each day
jfrom i+1 to n-1 (potential sell day): - Compute profit =
prices[j] - prices[i] - Update
maxProfitif this profit is larger - Return
maxProfit
Example Walkthrough
Code
- Time Complexity: O(n^2). We have two nested loops. The outer loop runs n times, and for each iteration, the inner loop runs up to n-1 times. This gives us roughly n * n / 2 comparisons, which is O(n^2).
- Space Complexity: O(1). We only use a couple of variables regardless of input size.
The wasted work sits in the inner loop: buy day i scans every future price, then buy day i+1 rescans nearly the same range. A single left-to-right pass removes the rescanning by carrying one value forward, the cheapest price seen so far.
Approach 2: One Pass (Optimal)
Intuition
Walk the array once while maintaining minPrice, the lowest price seen so far. The best transaction that sells on the current day buys at that minimum, so the profit available on each day is currentPrice - minPrice, and the answer is the largest of these values. One comparison per day replaces the brute force's inner loop.
Which day held the minimum is irrelevant; only the value matters. Because the scan moves left to right, minPrice reflects a day before the current one whenever a profit is computed, so the buy-before-sell constraint holds with no extra bookkeeping.
The code below also skips the profit check on any day that sets a new minimum. Nothing is lost: on such a day, price - minPrice would be negative, and maxProfit starts at 0 and never decreases.
Algorithm
- Initialize
minPriceto the first price (or infinity) - Initialize
maxProfitto 0 - For each price in the array:
- If the current price is less than
minPrice, updateminPrice - Otherwise, compute
profit = currentPrice - minPriceand updatemaxProfitif larger - Return
maxProfit
Example Walkthrough
Code
- Time Complexity: O(n). We make a single pass through the array, doing O(1) work at each step.
- Space Complexity: O(1). We only use two variables (
minPriceandmaxProfit) regardless of input size.
A different reformulation reaches the same O(n) bound: treat the profit as a sum of day-over-day price changes and apply Kadane's algorithm.
Approach 3: Kadane's Algorithm on Price Differences
Intuition
Define the day-over-day change diff[i] = prices[i] - prices[i-1]. Buying on day i and selling on day j earns prices[j] - prices[i], and that difference telescopes into the sum diff[i+1] + diff[i+2] + ... + diff[j]. Every transaction therefore corresponds to a contiguous run of daily changes, so the maximum profit equals the maximum subarray sum over the changes, where an empty run (no transaction, profit 0) is allowed.
This is the maximum subarray problem, which Kadane's algorithm solves in one pass. Maintain current, the best sum of a run ending on the current day. Extending yesterday's run by today's change gives current + diff; if that goes negative, reset current to 0, because a run with a negative total can only reduce any sum built on top of it. In stock terms, a reset moves the buy day forward past a drop that erased the accumulated gain.
For [7, 1, 5, 3, 6, 4], the changes are [-6, 4, -2, 3, -2]. The best run is 4 + (-2) + 3 = 5, the same transaction as buying at 1 and selling at 6.
Algorithm
- Initialize
current(best run sum ending today) andbestto 0 - For each day
ifrom 1 to n-1: - Compute
diff = prices[i] - prices[i-1] - Set
current = max(0, current + diff) - Set
best = max(best, current) - Return
best
Example Walkthrough
Code
- Time Complexity: O(n). One pass over the array, computing each day-over-day change as it is needed.
- Space Complexity: O(1). The change is computed on the fly, so no difference array is stored.
Both linear solutions are instances of a more general recurrence. Model each day with two states: hold, the best balance while owning the stock, updated as hold = max(hold, -price), and cash, the best balance without it, updated as cash = max(cash, hold + price). With one transaction allowed, hold equals the negative of minPrice and cash equals maxProfit, so the state machine is Approach 2 under different names. This form matters because adding states extends it to the harder variants of the problem: multiple transactions, cooldown periods, and transaction fees.