Best Time to Buy and Sell Stock (LeetCode 121)

The problem

You get an array prices where prices[d] is a stock’s price on day d. You may buy once and sell once, and the sale must come on a later day than the purchase. Return the largest profit you can make, or 0 if every possible trade loses money.

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

Buy on day 1 at price 1 and sell on day 4 at price 6, for a profit of 5.

How to think about it

Start with brute force. Try every buy day i and every later sell day j, and keep the largest prices[j] − prices[i]. That’s O(n²) pairs.

Flip the question around. Instead of asking “for this buy day, what’s the best sell day?”, ask “if I sell today, what’s the best day I could have bought?” The answer is obviously the cheapest day before today. So the best profit for selling today is today's price − lowest price so far.

The key insight: one number of memory is enough. You never need the whole history, only its minimum. Keep lo, the lowest price seen so far, and best, the largest gap seen so far. Each new price first updates lo, then checks whether selling today beats best. Updating lo first is fine: if today is the new minimum, the gap is 0, which never hurts.

Which pattern is this? A sliding window whose left edge jumps to the minimum: the window is “from the cheapest day so far up to today”. You’ll also see it called Kadane-style or a running-minimum scan. The tell is “best pair (i, j) with i < j, where the score is a difference”.

Approach

1. Set lo = infinity and best = 0.
2. For each price p, set lo = min(lo, p).
3. Set best = max(best, p - lo).
4. Return best.

Solution

def max_profit(prices):
    lo = float('inf'); best = 0
    for p in prices:
        lo = min(lo, p); best = max(best, p - lo)   # cheapest buy so far; sell today
    return best
# max_profit([7,1,5,3,6,4]) -> 5

Dry run

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

The answer is 5.

Complexity

• Time: O(n). One pass, constant work per day.
• Space: O(1). Two numbers, whatever the input size.

Edge cases and pitfalls

• Prices only fall ([7, 6, 4, 3, 1]): every gap is 0, so return 0. Don’t return a negative number.
• Empty or single-day input returns 0; there’s no valid trade.
• Taking max(prices) − min(prices) is wrong when the maximum comes before the minimum, as in [5, 1].
• Updating best before lo also works, but only because a same-day trade is worth 0. Keep the order clear in your head.
• This is not the multi-trade version. If you can trade many times (LeetCode 122), you instead add every upward step.

Related problems

• Maximum Subarray (LeetCode 53): Kadane’s algorithm, the same one-pass “best ending here” idea on sums.
• Maximum Average Subarray I (LeetCode 643): a fixed-size sliding window to compare with this flexible one.
• Daily Temperatures (LeetCode 739): another “compare today with earlier days” scan, solved with a monotonic stack.