Best single buy-then-sell on a price history

Sliding window Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
prices = [7, 1, 5, 3, 6, 4]
low, best = prices[0], 0
for p in prices[1:]:
    best = max(best, p - low)
    low = min(low, p)
print(best, low)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 5 1

Right: buy at 1 and sell at 6; the minimum stays 1.

The running minimum drops to 1 on day two and the best gap after it is 6 - 1.

Why not the others?
  • B 6 1. 7 comes before 1, so 7 - 1 is a loss, not a profit of 6.
  • C 4 1. Selling at 6 beats selling at 5.

30-second answer

Scan the days once, keeping the lowest price seen so far. Each day's best sale is today's price minus that minimum; keep the largest. This is a window whose left edge jumps to any new minimum. O(n) time, O(1) space.

Practise saying it · 30 s. No recording, just a timer

Explain the running-minimum scan.

Say your answer out loud, then check which of these points you covered:

  • Cheapest earlier day
  • Profit per day
  • O(n), O(1)

Deep dive

The minimum must come before the sale day, which is why it is updated after computing today's profit (or the order does not matter when profit is clamped at 0).

Checking every buy and sell pair is O(n²).

Equivalent view: the largest sum of consecutive day-to-day changes, which is Kadane's algorithm on differences.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def best_profit(prices: list[int]) -> int:
    best = 0
    low = prices[0] if prices else 0
    for p in prices:
        best = max(best, p - low)
        low = min(low, p)
    return best

Common mistakes

  • Taking max(prices) - min(prices) without checking that the minimum comes first.
  • Returning a negative number when prices only fall.

Senior take & follow-ups

Say why the running minimum is enough: the best buy for any sale day is the cheapest earlier day.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if you may trade many times?

    Show hint

    Add up every positive day-to-day rise.

  2. What about at most two trades?

    Show hint

    Track four running states, or best profit to the left and right of each day.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.