DSA Best Time to Buy and Sell Stock

The problem

Best Time to Buy and Sell Stock picks one buy day and one later sell day. The profit is the sell price minus the buy price. The task is the largest profit from a single pair of days.

Buying is never forced. A list of prices that only falls answers zero. At most one buy and one sell are allowed.

cases = [
    ([7, 1, 5, 3, 6, 4], 5),
    ([7, 6, 4, 3, 1], 0),
    ([9, 4, 7, 3, 8, 5, 6], 5),
    ([1, 2], 1),
    ([2, 4, 1], 2),
]
for prices, expected in cases:
    print(prices, 'best profit:', expected)

Intuition

The first idea pairs the cheapest price with the highest price. Subtract the minimum from the maximum. That pair ignores order, and order is the whole problem.

The highest price can sit before the cheapest price. Selling before buying is impossible. The trap below makes that pair look better than any legal pair.

prices = [9, 2, 8, 1]
print('highest price:', max(prices), 'on day', prices.index(max(prices)) + 1)
print('lowest price:', min(prices), 'on day', prices.index(min(prices)) + 1)
print('max minus min:', max(prices) - min(prices))
print('that sell day comes before that buy day, so the pair is illegal')

Brute force

The brute force tries every legal pair. The buy day comes first. Every later day is a possible sell day.

def best_brute(prices):
    best = 0
    pairs = 0
    for buy in range(len(prices)):
        for sell in range(buy + 1, len(prices)):
            pairs += 1
            profit = prices[sell] - prices[buy]
            if profit > best:
                best = profit
    return best, pairs

for prices in [[7, 1, 5, 3, 6, 4], [7, 6, 4, 3, 1], [2, 4, 1]]:
    best, pairs = best_brute(prices)
    print(prices, 'best:', best, 'pairs tried:', pairs)

The answer is correct. The pair count is the problem. Doubling the days roughly quadruples the pairs.

The optimal solution: track the lowest price so far

The key idea is one pass with a running low. For each price, the best sell on that day pairs it with the lowest price seen before it.

def max_profit(prices):
    if not prices:
        return 0
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        if price - lowest > best:
            best = price - lowest
    return best

cases = [[7, 1, 5, 3, 6, 4], [7, 6, 4, 3, 1], [9, 4, 7, 3, 8, 5, 6], [1, 2], [2, 4, 1]]
for prices in cases:
    print(prices, 'best profit:', max_profit(prices))

Walkthrough

Take the prices [7, 1, 5, 3, 6]. Each day updates the low first. The same day then tests a sale against that low.

prices = [7, 1, 5, 3, 6]
lowest = prices[0]
best = 0
for day in range(len(prices)):
    price = prices[day]
    if price < lowest:
        lowest = price
    if price - lowest > best:
        best = price - lowest
    print('day', day + 1, 'price', price, 'lowest', lowest, 'best', best)

Day 2 drops the low to 1. Day 3 tests 5 - 1 and sets the best profit to 4. Day 5 tests 6 - 1 and raises the best profit to 5.

Complexity

Time is O(n). Each price is visited once, with one low update and one profit test.

Space is O(1). The pass stores only the lowest price and the best profit.

def pair_count(n):
    return n * (n - 1) // 2

for n in [10, 20, 40]:
    print('days', n, 'brute pairs:', pair_count(n), 'one-pass visits:', n)

Edge cases and pitfalls

A single price allows no pair. The answer is zero, because a sell day after the buy day does not exist. An empty list also answers zero in the guarded version.

Updating the best profit before the low is a subtle slip on the first day only. The guarded order in this article updates the low first. Both orders agree after the start, since a price minus itself is zero.

def max_profit(prices):
    if not prices:
        return 0
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        if price - lowest > best:
            best = price - lowest
    return best

print('empty:', max_profit([]))
print('single:', max_profit([5]))
print('only falls:', max_profit([5, 4, 3, 2]))
print('flat:', max_profit([3, 3, 3]))
print('rises at once:', max_profit([1, 5, 2]))