4.6.1 — Best Time to Buy and Sell Stock

LeetCode 121 · Easy · ★ Blind 75

The problem

prices[i] is the price on day i. Buy on one day and sell on a later day. Return the largest profit possible, or 0 if no profit can be made.

[7, 1, 5, 3, 6, 4]   →  5    (buy at 1 on day 1, sell at 6 on day 4)
[7, 6, 4, 3, 1]      →  0    (prices only fall)

Up to 100,000 days.

The pattern

For any selling day, the best profit is that day's price minus the cheapest price seen before it. So walk forward, remember the cheapest price so far, and at each day work out what selling today would earn.

That is one pass with one variable. You never need to look backwards, because the only thing the past can tell you is its minimum, and you already have it.

The solution

PythonTypeScript

python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cheapest = float('inf')
        best = 0

        for price in prices:
            cheapest = min(cheapest, price)
            best = max(best, price - cheapest)

        return best

function maxProfit(prices: number[]): number {
  let cheapest = Infinity, best = 0;

  for (const price of prices) {
    cheapest = Math.min(cheapest, price);
    best = Math.max(best, price - cheapest);
  }

  return best;
}

Updating cheapest before computing the profit looks like it could let you buy and sell on the same day. It can — but that profit is exactly 0, and best starts at 0, so it never changes the answer. Writing it this way removes a branch.

best starting at 0 is what makes the falling-prices case return 0 rather than a negative number.

Trace

[7, 1, 5, 3, 6, 4]

price	cheapest	profit today	best
7	7	0	0
1	1	0	0
5	1	4	4
3	1	2	4
6	1	5	5
4	1	3	5

Complexity

$O(n)$ time, $O(1)$ space.

Is this really a sliding window?

NeetCode files it under sliding window, and you can read it that way: a window from the buy day to the sell day, where the left edge jumps forward whenever a cheaper price appears.

But it is cleaner to see it as carrying the best answer so far, which is the seed of dynamic programming. At each day you ask "what is the best I can do ending here", using only the answer for the previous day. That is exactly the shape of 4.23, and the connection is worth holding onto.

Related, and worth noticing: Maximum Subarray (Kadane's algorithm) is the same code on differences. If you took the daily price changes and found the largest-sum contiguous stretch, you would get this same answer.

Where this goes next

The variations are a small ladder, and each one changes the state you have to carry:

Buy and Sell Stock II — unlimited transactions. Take every upward step. Greedy, and provably optimal. 4.26.
With Cooldown — you cannot buy the day after selling. Now you need to track which state you are in (holding, sold, free), and it becomes DP. 4.24.
With a transaction fee, and at most k transactions — more state again.

The ladder is a good illustration of when greedy stops working and DP takes over: as soon as today's best choice depends on a restriction created by an earlier choice, greed fails. 4.22 makes that test precise.

Next: 4.6.2 Longest Substring Without Repeating Characters — the first real window, with a rule for when the left edge moves.

4.6.1 — Best Time to Buy and Sell Stock ​

The problem ​

The pattern ​

The solution ​

Trace ​

Complexity ​

Is this really a sliding window? ​

Where this goes next ​