Stock Buy and Sell for Maximum Profit in Python: O(n) Single Pass

You are given a list of stock prices where prices[i] is the price on day i. Find the maximum profit you can make by buying on one day and selling on a later day. You must buy before you sell, and only one transaction is allowed.

This problem appears in almost every algorithm interview collection. The naive solution is O(n²). The optimal solution is a single O(n) pass.

The Naive Approach — O(n²)

Check every possible buy-sell pair. Works, but slow for large inputs.

def max_profit_naive(prices):
    """O(n²) brute force — check all buy/sell combinations."""
    max_profit = 0

    for buy_day in range(len(prices)):
        for sell_day in range(buy_day + 1, len(prices)):
            profit = prices[sell_day] - prices[buy_day]
            if profit > max_profit:
                max_profit = profit

    return max_profit

prices = [7, 1, 5, 3, 6, 4]
print(max_profit_naive(prices))   # Output: 5

The Optimal Approach — O(n) Single Pass

Track the minimum price seen so far. At each day, compute what profit you would make if you sold today (current price minus the running minimum). Keep the highest such profit.

def max_profit(prices):
    """
    Single-pass O(n) solution.
    Track minimum price and maximum profit simultaneously.
    """
    if len(prices) < 2:
        return 0

    min_price = prices[0]
    best_profit = 0

    for price in prices[1:]:
        if price < min_price:
            min_price = price              # found a better buy day
        else:
            profit = price - min_price
            if profit > best_profit:
                best_profit = profit       # found a better sell day

    return best_profit

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

Walking through [7, 1, 5, 3, 6, 4]:

Day 0: min = 7, profit = 0
Day 1: price 1 < min → min = 1
Day 2: price 5, profit = 4 → best = 4
Day 3: price 3, profit = 2 → no change
Day 4: price 6, profit = 5 → best = 5
Day 5: price 4, profit = 3 → no change

Answer: 5.

Edge Cases

# Prices only fall — no profitable trade
print(max_profit([7, 6, 4, 3, 1]))   # 0

# One price — cannot trade
print(max_profit([5]))               # 0

# All same price
print(max_profit([3, 3, 3, 3]))     # 0

# Only two prices — buy day 0, sell day 1
print(max_profit([1, 9]))            # 8

Also Return the Buy and Sell Days

def max_profit_with_days(prices):
    """Return (profit, buy_day, sell_day)."""
    if len(prices) < 2:
        return 0, -1, -1

    min_price = prices[0]
    min_day = 0
    best_profit = 0
    buy_day = 0
    sell_day = 0

    for i in range(1, len(prices)):
        if prices[i] < min_price:
            min_price = prices[i]
            min_day = i
        elif prices[i] - min_price > best_profit:
            best_profit = prices[i] - min_price
            buy_day = min_day
            sell_day = i

    return best_profit, buy_day, sell_day

profit, buy, sell = max_profit_with_days([7, 1, 5, 3, 6, 4])
print(f"Profit: {profit}, Buy on day {buy} (price {[7,1,5,3,6,4][buy]}), "
      f"Sell on day {sell} (price {[7,1,5,3,6,4][sell]})")
# Output: Profit: 5, Buy on day 1 (price 1), Sell on day 4 (price 6)

Multiple Transactions (Harder Variant)

If you can make as many transactions as you want (but only hold one stock at a time), sum up every upward slope:

def max_profit_multiple(prices):
    """Multiple transactions — capture every upward movement."""
    total_profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            total_profit += prices[i] - prices[i - 1]

    return total_profit

print(max_profit_multiple([7, 1, 5, 3, 6, 4]))
# Output: 7  (buy at 1, sell at 5; buy at 3, sell at 6)

This greedy approach works because every upward segment represents a profitable trade, and capturing them all individually is equivalent to buying at each local minimum and selling at each local maximum.

Complexity Summary

Version	Time	Space
Brute force	O(n²)	O(1)
Single pass (optimal)	O(n)	O(1)
Multiple transactions	O(n)	O(1)