Best Time to Buy and Sell Stock — LeetCode Solution in Python

The problem, in short

You are given a list of daily prices for one stock. You may buy on one day and sell on a later day, at most once. Return the largest profit available; if no buy/sell pair produces a profit, return 0.

The constraint that matters is the ordering: you cannot sell before you buy.

How to think about it

It is tempting to reach for max(prices) - min(prices), and that is wrong whenever the maximum occurs before the minimum — [9, 1] would report a profit of 8 on a trade you cannot make. Any correct solution has to respect the direction of time.

So reframe it per day. If I sell today, my best possible profit is today's price minus the cheapest price I have seen so far. I can compute that in constant time if I carry the running minimum with me. The answer is the best of those per-day figures.

The running minimum can only look backwards, which is precisely what enforces “buy before sell” — the constraint is satisfied by the structure of the loop, not by an extra check.

The brute-force approach

Try every buy day against every later sell day and keep the best difference.

def max_profit_brute(prices):
    best = 0
    for buy in range(len(prices)):
        for sell in range(buy + 1, len(prices)):
            best = max(best, prices[sell] - prices[buy])
    return best

Correct, and O(n²). On the long price histories these problems use, it is too slow — but notice what the inner loop actually computes: for a fixed buy day it scans forward for the best sell. Flipping that around, so each sell day looks back at the best buy, is what collapses it to one pass.

The optimised approach

Walk the prices once, carrying two values: the cheapest price seen so far, and the best profit found so far. For each price, work out what selling today would earn, update the best profit if that beats it, then update the running minimum for the days still to come.

Python solution

def max_profit(prices):
    """Return the best profit from a single buy followed by a later sell."""
    if not prices:
        return 0

    cheapest = prices[0]     # lowest price seen so far
    best = 0                 # 0 means "make no trade at all"

    for price in prices[1:]:
        # Selling today, against the cheapest day behind us.
        best = max(best, price - cheapest)
        cheapest = min(cheapest, price)

    return best

Time and space complexity

One pass and two scalars. Nothing is stored per element, so the space is constant — this is the rare case where the linear solution is also the cheapest one in memory, with no trade-off to make.

Example walkthrough

Take prices = [7, 1, 5, 3, 6, 4].

The answer is 5 — buy at 1 on day 1, sell at 6 on day 4. The price of 7 on day 0 is never a candidate buy after day 1, because the running minimum has already replaced it.

Common mistakes

1. Using max(prices) - min(prices). This ignores order. On [9, 1] it returns 8 for a trade that would require selling before buying.
2. Updating the minimum before computing the profit. If cheapest is updated first, today's price can be compared against itself and the profit for a single day becomes 0 rather than being measured against a genuinely earlier day. Compute the profit, then update.
3. Initialising best profit to a negative number. The problem says to return 0 when no profitable trade exists. Starting from float('-inf') reports a loss on a falling market like [5, 4, 3], which should be 0.
4. Not handling an empty or single-element list. Both should return 0. Indexing prices[0] without the guard raises IndexError.

Related problems

• Maximum Subarray — Kadane's algorithm — the same “best ending here” shape.
• Best Time to Buy and Sell Stock II — Unlimited trades turns it into a sum of every upward step.
• Container With Most Water — Another problem where the naive answer ignores a positional constraint.

More write-ups are indexed in Boopathi's LeetCode solutions.