LeetCode 121 · Sliding Window

Best Time to Buy and Sell Stock, explained with a picture

Buying the dip on a price chart.

EasySliding Window
▶ Watch it step by step

The problem

You get a list of a stock’s price on each day. Choose one day to buy and a later day to sell to make the most profit. If no profit is possible, return 0.

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

Picture it

Picture a price chart with one bar per day. We walk forward through time with a finger marking the cheapest day so far (the dip). Each new day we ask: “if I had bought at that dip and sold today, how much would I make?” We keep the best answer. If today is even cheaper, the dip moves here.

How to recognise it

  • You choose two moments, an earlier one and a later one, and the score is later minus earlier.
  • For each possible later day, only one earlier day matters: the cheapest one so far.
  • "The best so far" can be carried along in one variable as you walk the list, like the left edge of a window that only moves to a cheaper day.
  • Up to 10^5 prices, so checking every pair of days is too slow.

Start with brute force

Try every buy day i and every later sell day j, and keep the largest profit. Start at 0, since you may choose not to trade.

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

There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). With n = 10^5 that is about 5 × 10^9 pairs, far too slow.

From brute force to the idea

  1. Fix the sell day instead. For a sell day j, the best buy day is the cheapest day before j. The other earlier days cannot do better.
  2. Find the waste. The brute force recomputes "the cheapest earlier day" for every j by rescanning, but it only changes when a new low price appears.
  3. Carry the minimum. Keep cheapest, the lowest price seen so far. For each new price p, the best profit from selling today is p - cheapest.
  4. Then update. After checking, set cheapest = min(cheapest, p). Checking first means you never sell on the day you buy; here that would only give 0, so the order is safe either way.
  5. Start at 0. If prices only fall, every p - cheapest is negative or zero, and best stays 0, which is what the problem asks for.

This is the key idea: for each day, the best trade ending today buys at the cheapest price seen so far.

The key idea

Track the minimum price so far and the best (today − minimum). One pass, O(n).

Python solution

def max_profit(prices):
    if not prices: return 0      # no days
    cheapest, best = prices[0], 0
    for p in prices[1:]:    # sell or rebuy?
        best = max(best, p - cheapest)
        cheapest = min(cheapest, p)
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every buy and sell pairO(1): one best value
Running minimum (shown code)O(n): one pass with two comparisons per dayO(1) extra besides prices[1:], which copies the list (O(n)); looping over indices avoids that copy

Edge cases

  • Empty list: the guard if not prices: return 0 handles it. LeetCode guarantees at least one price.
  • One day: returns 0; there is no later day to sell on.
  • Falling prices ([7, 6, 4, 3, 1]): returns 0, no trade.
  • Flat prices ([3, 3, 3]): returns 0.
  • New low after the best trade ([2, 4, 1]): returns 2. The later low of 1 has no higher day after it, so the earlier trade stands.
  • New low that leads to a better trade ([2, 4, 1, 7]): returns 6, buying at 1.

Common mistakes

  • Returning max(prices) - min(prices). The maximum may come before the minimum: [5, 1] gives 4, but you cannot sell before you buy, so the answer is 0.
  • Starting best at -inf or at prices[1] - prices[0], which returns a loss instead of 0 when prices only fall.
  • Resetting best whenever a new low appears, which throws away a good trade made earlier.
  • Starting cheapest at 0, which makes every price look like profit.
Your turn: strictly increasing pair

Return the largest nums[j] - nums[i] with i < j and nums[i] < nums[j], or −1 if no such pair exists. For [7, 1, 5, 4] the answer is 4; for [9, 4, 3, 2] and [5, 5] it is −1. Describe your approach, then write it if you like.

Compare with our answer

Same running minimum. The only changes are the starting value (−1 means "nothing found yet") and the condition: a day only counts if it is strictly above the minimum, so equal values never produce a 0.

def maximum_difference(nums):
    best, low = -1, nums[0]
    for x in nums[1:]:
        if x > low:
            best = max(best, x - low)
        low = min(low, x)
    return best

Time O(n), space O(1) apart from the slice. It assumes at least two numbers.

A strong answer mentions: reusing the running minimum, the strict > so that equal values are rejected, and −1 as the "no pair" start.

Check what stuck

1. You must maximise values[i] + values[j] + i - j over pairs i < j. Which approach fits best?

2. Why does the shown code never need to look back at earlier days?

3. A learner returns max(prices) - min(prices). Which input now gets a wrong answer?

Score 60% or more and the lesson is marked complete.