Best Time to Buy and Sell Stock

You are given a list prices where prices[i] is the price of a stock on day i. You want to maximize profit by choosing one day to buy and a later day to sell.

Return the maximum profit you can achieve. If no profit is possible, return 0.

Examples

Input:  [7,1,5,3,6,4]
Output: 5      # buy at 1 (day 1), sell at 6 (day 4)

Input:  [7,6,4,3,1]
Output: 0      # prices only fall — never buy

Constraints

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

Approach — track the minimum so far

The naive approach tries every buy/sell pair — O(n^2). The key insight: to sell on day i for maximum profit, you'd have bought on the cheapest day before i. So sweep left to right, remember the lowest price seen so far, and at each day compute the profit if you sold today. Keep the best.

Solution

def max_profit(prices: list[int]) -> int:
    min_price = float("inf")
    best = 0
    for price in prices:
        if price < min_price:
            min_price = price          # new cheapest buy day
        else:
            best = max(best, price - min_price)  # sell today
    return best

Explanation

• min_price is the best price to have bought at among all earlier days.
• On each day you make one decision: either this is a new cheapest buy point, or you consider selling into the running minimum. You never need to look backward — the running minimum already captures the best past buy.
• Profit can never be negative because best starts at 0 and we only update it with non-negative differences.

Complexity

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

Interview tips

This is the gateway to Kadane's-algorithm-style "best subarray" thinking. A common follow-up allows multiple transactions (buy/sell repeatedly) — there the answer is the sum of every positive day-to-day increase.