DSAMotivator

Best Time to Buy and Sell Stock

EasyĀ·šŸŖŸ Sliding WindowĀ·Open on LeetCode ā†—

Given a series of daily prices, buy on one day and sell on a later one to make the largest possible profit, or make none at all.

prices = [8, 3, 6, 2, 9, 4]step 1/14
8
3
6
2
9
4
0
1
2
3
4
5

Walk forward carrying two numbers: the cheapest day so far, and the best profit so far.

1def max_profit(prices):
2    cheapest = float("inf")
3    best = 0
4    for price in prices:
5        cheapest = min(cheapest, price)
6        best = max(best, price - cheapest)
7    return best
Read the 14 steps as text
  1. 1Walk forward carrying two numbers: the cheapest day so far, and the best profit so far.
  2. 2Day 0, price 8.
  3. 38 is the lowest price yet. Any future sale is measured against it.
  4. 4Day 1, price 3.
  5. 53 is the lowest price yet. Any future sale is measured against it.
  6. 6Day 2, price 6.
  7. 7Buy at 3, sell at 6 ā€” profit 3, the best so far.
  8. 8Day 3, price 2.
  9. 92 is the lowest price yet. Any future sale is measured against it.
  10. 10Day 4, price 9.
  11. 11Buy at 2, sell at 9 ā€” profit 7, the best so far.
  12. 12Day 5, price 4.
  13. 13Selling here makes 2, which doesn't beat 7.
  14. 14The best trade available was 7.

The idea

Trying every buy day against every sell day is O(nĀ²), and it spends nearly all of that time re-answering one question: what was the cheapest price before today?

So carry that answer instead of recomputing it. Walk forward, remember the lowest price seen so far, and at each day ask what selling today would earn against that low.

The reason this is safe ā€” and it is exactly what an interviewer is checking ā€” is that the cheapest price seen so far is always at an earlier index than today. The buy-before-sell constraint is satisfied automatically by the direction of the walk, never by an explicit check.

It's worth seeing that these two updates can be done in either order within a day. Updating the low first allows a same-day buy and sell, which earns zero and can never beat a real profit, so it costs nothing.

The approach

  1. 1Track the cheapest price seen so far and the best profit so far.
  2. 2For each day, first lower the cheapest price if today undercuts it.
  3. 3Then check what selling today would make against that cheapest price, and keep it if it beats the current best.
  4. 4Return the best, which stays 0 if prices only ever fall.

Complexity

Time
O(n)
Space
O(1)

One pass and two numbers. No pair of days is ever compared directly.

Code

def max_profit(prices):
    cheapest = float("inf")
    best = 0
    for price in prices:
        cheapest = min(cheapest, price)
        best = max(best, price - cheapest)
    return best

What goes wrong

  • ā€¢Returning the largest difference between any two prices regardless of order. Selling before buying is not a trade, and on a falling series that mistake returns a large positive number instead of 0.
  • ā€¢Initialising the best profit to a negative sentinel. Doing nothing is always allowed, so the floor is 0.
  • ā€¢Confusing this with the version that allows unlimited transactions, where the answer is simply the sum of every upward step.