Best Time to Buy and Sell Stock: 5 Powerful Tactics

This looks like a finance quiz. It's not. It's a minimum-tracking puzzle wearing a stock costume.

New candidates reach for nested loops. For each buy day, scan every later sell day. That's O(n^2), and it dies on 100,000-price inputs. You'll burn 15 minutes coding it, then watch it time out.

The one-pass fix needs two variables. Track the lowest price seen so far. Track the best profit seen so far. Each day, update the minimum, then check today's spread against the best. That's O(n) time, O(1) space, and about eight lines. Don't memorize it — understand the invariant and you'll never forget it.

Buy Once, Sell Later: What That Constraint Really Forbids

Given prices where prices[i] is the stock price on day i, pick one buy day and one later sell day to maximize prices[sell] - prices[buy]. Return the profit, or 0 if no profitable trade exists. Example: [7,1,5,3,6,4] gives 5 (buy at 1 on day 2, sell at 6 on day 5). Falling input [7,6,4,3,1] gives 0 — you simply don't trade.

Constraints: up to 10^5 prices, each up to 10^4. O(n^2) pairs mean ~5×10^9 comparisons — hopeless. The answer fits in a plain integer, and only one transaction is allowed (LeetCode 121; unlimited trades is problem 122).

Walk [7,1,5,3,6,4]: min=7, profit=0 → price 1: min=1 → price 5: profit=4 → price 3: profit stays 4 → price 6: profit=5 → price 4: stays 5. Answer 5. The running minimum summarizes everything left of today.

Every Buy-Sell Pair Is O(n^2) and Times Out at 10^5 Prices

Brute force: for each buy day i, scan every sell day j > i, keep the max spread. That's n(n-1)/2 pairs — O(n^2) time, O(1) space. At n = 10^5 the pair count hits ~5×10^9; Python needs minutes per 10^8 simple ops, so this never finishes. Even n = 10^4 (50M pairs) takes ~8 seconds against a 2-second limit.

Its interview value is one sentence: 'All pairs is O(n^2) — too slow for 10^5 prices, so I'll track the running minimum instead.' Say it, skip the code, and go straight to the pass. Writing the loops first signals you didn't read the constraints.

Track the Minimum So Far and Sell Against It Each Day

Observe: the best profit from selling on day i is prices[i] minus the minimum price on days 0..i. So maintain that minimum as you sweep. Initialize min_price = prices[0], best = 0. For each price: min_price = min(min_price, price), then best = max(best, price - min_price). Updating min first is safe — using today's price as its own buy gives spread 0, never beating best.

Proof sketch: any optimal trade (b, s) sells on day s. On day s the running min equals the true prefix minimum m ≤ prices[b], so the algorithm records prices[s] - m ≥ prices[s] - prices[b] = optimal. It never overestimates either, since min_price is always a real earlier price. Hence the recorded max equals the optimum. Each day does O(1) work: O(n) time, two variables: O(1) space.

This is also Kadane's algorithm on daily differences in disguise — but the min-price telling is shorter and extends naturally to k-transaction DP.

The One-Pass Solution in Full Python

The code above is the complete LeetCode submission. Trace [7,1,5,3,6,4]: min=7,best=0 → 1: min=1 → 5: spread 4, best=4 → 3: spread 2 → 6: spread 5, best=5 → 4: spread 3. Returns 5. Trace [7,6,4,3,1]: spreads never positive, returns 0.

Complexity: O(n) time, O(1) space. No imports, no slicing, no nested loops — safe past n = 10^5.

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if len(prices) < 2:
            return 0
        min_price = prices[0]
        best = 0
        for price in prices[1:]:
            if price < min_price:
                min_price = price
            spread = price - min_price
            if spread > best:
                best = spread
        return best

Monotonically Falling Prices and the Zero-Profit Case

Empty list and single price both return 0 via the early guard. Strictly falling returns 0 — never negative. All-equal returns 0. Minimum at the last index (e.g. [3,2,5,4,1]) still returns the best earlier spread (3), because best is sticky while min keeps dropping.

Large-input trap: max(prices[i+1:]) inside a loop re-scans the suffix daily — O(n^2) disguised as one loop. Integer overflow is a non-issue in Python but mention it for Java/C++ follow-ups (use long or clamp). Duplicate minima need no special handling: re-recording the same min changes nothing.

Why One Pass With Two Variables Is the Floor

Time O(n): each price is read once with O(1) work. Space O(1): two integers beyond the input. Both are optimal — every price must be examined (time lower bound), and the answer needs only the running min and best spread (space lower bound).

Whiteboard closer: 'One pass, two variables, optimal in both dimensions.' Then offer the follow-up unprompted: 'With unlimited trades I'd sum positive day-to-day gains; with k trades I'd use a state-machine DP.' That sentence turns a pass into a strong hire.