Best Time to Buy and Sell Stock

Problem

You are given an array prices where prices[i] is the price of a stock on day i. You may make at most one transaction: pick one day to buy a single share and a later day to sell it. Return the maximum profit you can achieve. If no profitable transaction exists (prices only fall), return 0 — you are allowed to skip trading entirely.

Note the ordering constraint: the sell day must come strictly after the buy day. You cannot sell first and buy later.

Examples

• prices = [7, 1, 5, 3, 6, 4] → 5 — buy at 1 (day 1), sell at 6 (day 4); profit 6 - 1 = 5.
• prices = [7, 6, 4, 3, 1] → 0 — prices only decline, so the best move is not to trade.
• prices = [2, 4, 1, 7] → 6 — buy at 1 (day 2), sell at 7 (day 3); note the tempting 2 → 4 early pair is worse.

Constraints

• 1 <= len(prices) <= 10^5
• 0 <= prices[i] <= 10^4

With up to 10^5 days, checking every buy/sell pair (~5 * 10^9 pairs in the worst case) is too slow — the expected solution is a single pass.

Think about it first

TL;DR

One-pass sliding window (track the minimum buy price so far) — O(n) time, O(1) space.

Approach 1 — Brute force

Try every (buy day, sell day) pair with buy before sell and keep the best difference.

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

Complexity: O(n²) time, O(1) space. With n = 10^5 that is on the order of 5 * 10^9 comparisons — far past the time limit.

Approach 2 — Sliding window over (buy, sell) days

The insight: if the price at the current day drops below the price at our chosen buy day, then every future sale would do better buying at the current day instead. So the buy pointer only ever jumps forward — it never pays to move it back. Both pointers move monotonically left-to-right, which is exactly the sliding-window shape.

def maxProfit(prices: list[int]) -> int:
    best = 0
    left = 0                      # buy day
    for right in range(1, len(prices)):   # sell day
        if prices[right] < prices[left]:
            left = right          # a cheaper buy day; window restarts here
        else:
            best = max(best, prices[right] - prices[left])
    return best

Walkthrough on prices = [7, 1, 5, 3, 6, 4]:

The window [left, right] grows while it stays “valid” (buy price is the cheapest seen) and collapses to a single day the moment a cheaper buy appears.

Complexity: O(n) time, O(1) space.

Approach 3 — Min-so-far (same idea, tighter code)

The insight: the left pointer above always sits on the minimum price seen so far, so we can store that value instead of an index.

def maxProfit(prices: list[int]) -> int:
    min_price = prices[0]
    best = 0
    for p in prices[1:]:
        if p < min_price:
            min_price = p
        else:
            best = max(best, p - min_price)
    return best

Complexity: O(n) time, O(1) space. Identical work to Approach 2 — just a different bookkeeping style.

Common pitfalls

• Selling before buying. max(prices) - min(prices) is wrong when the maximum comes before the minimum (e.g. [9, 1, 3] — answer is 2, not 8).
• Forgetting the no-trade option. On a strictly decreasing array the answer is 0, not the least-negative loss. Initializing best = 0 handles this.
• Updating best before updating the buy day. Compare against the min seen so far including earlier days only — the code above is safe because a new minimum can’t also be a profitable sell against itself.

Pattern takeaway

This is a minimal form of a variable-size window: the window is anchored at the best candidate left endpoint, and the key argument is monotonicity — once a better left endpoint appears, the old one is dominated for every future right endpoint, so the left pointer never moves backward. A left pointer that never backtracks is what keeps a sliding-window scan linear.