Best Time to Buy and Sell Stock

The problem

You have an array prices where prices[i] is the price of a stock on day i. You may complete at most one transaction (buy once, sell once, with the sell strictly after the buy). Return the maximum profit; if no profit is possible, return 0.

Pattern: single pass with a running extremum

The trick is to stop thinking "find the best (buy, sell) pair" and start thinking "at each day, what's the best price I could have bought at so far?" That reframes the problem as a single pass that maintains a running minimum.

This pattern shows up everywhere a problem asks for "best (something) up to position i" — running min/max with constant state. If the question generalizes to maintaining a running window of statistics, the natural extension is a monotonic deque (the sliding-window-maximum pattern).

Brute force: every pair

Two nested loops — try every buy day, then every sell day after it. O(n^2) time, O(1) space. Correct but slow on million-element arrays.

def max_profit_brute(prices: list[int]) -> int:
    best = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, prices[j] - prices[i])
    return best

Optimal: O(n) single pass

def max_profit(prices: list[int]) -> int:
    min_so_far = float('inf')
    best = 0
    for p in prices:
        min_so_far = min(min_so_far, p)
        best = max(best, p - min_so_far)
    return best

Trace

prices = [7, 1, 5, 3, 6, 4]

p = 7   min_so_far = 7   profit = 0     best = 0
p = 1   min_so_far = 1   profit = 0     best = 0
p = 5   min_so_far = 1   profit = 4     best = 4
p = 3   min_so_far = 1   profit = 2     best = 4
p = 6   min_so_far = 1   profit = 5     best = 5    ← buy day 1, sell day 4
p = 4   min_so_far = 1   profit = 3     best = 5

return 5

Complexity

• Time: O(n) single pass.
• Space: O(1).

Variations worth knowing

• At most two transactions: requires a small DP with four states (held/sold × 1st transaction/2nd transaction). Still O(n).
• Unlimited transactions, no cooldown: sum all positive differences between consecutive days. Greedy works.
• With cooldown (must wait one day after selling): a state-machine DP — three states (held, sold, idle), three transitions per day.
• At most k transactions: O(nk) DP. The classic generalization, sometimes called the "Hadar problem."