Best Time to Buy and Sell Stock: One Pass Solution

You are given an array of stock prices where prices[i] is the price on day i. You can buy on one day and sell on a later day. Find the maximum profit you can make from a single transaction. If no profit is possible, return 0.

This is LeetCode 121: Best Time to Buy and Sell Stock, one of the most popular easy problems on the platform. It is also one of the best examples of how a single insight can take you from a slow brute force to a clean one-pass solution.

The brute force approach

The obvious approach is to try every possible pair of buy and sell days. For each day i, check every later day j and compute prices[j] - prices[i]. Track the maximum.

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

This works, but it is O(n^2). For an array with 100,000 prices, that is 5 billion comparisons. LeetCode will time out.

The redundancy here is that you keep re-scanning the right side of the array for each starting point. But you do not actually need to check every pair. There is a much simpler way to think about it.

The key insight: track the running minimum

Here is the idea. As you walk through the array from left to right, keep track of the lowest price you have seen so far. At each new price, the best you could do by selling today is price - min_price_so_far. Update your max profit if that is better than what you have.

That is it. One variable for the running minimum, one variable for the best profit. One pass through the array.

Why does this work? Because the optimal buy day is always before the optimal sell day. If you are at day i and considering selling, the best possible buy price is the minimum of everything before (and including) day i. You do not need to go back and check - you have been tracking it all along.

Walking through it step by step

Let's trace through the example prices = [7, 1, 5, 3, 6, 4]. We track two things: min_price (the lowest price seen so far, shown in purple) and max_profit (the best profit found so far). The green pointer shows the current day.

The answer is 5. Buy at price 1 (day 1), sell at price 6 (day 4).

Notice how we never looked backwards. Each element was visited exactly once, and we made our decision on the spot using only the running minimum. That is the power of tracking state as you go.

The code

Here is the one-pass solution in Python:

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)

    return max_profit

Six lines of logic. No nested loops, no extra data structures. Just two variables and a single scan.

Let's break down what is happening:

1. Start with min_price set to infinity so any real price will be smaller.
2. For each price, check: is this a new minimum? If yes, update min_price. We would never sell at a new low, so we skip the profit check.
3. If it is not a new minimum, compute the profit from buying at min_price and selling now. Update max_profit if this beats our current best.
4. Return max_profit at the end. If prices only went down, we never found a profit and return 0.

A slight variant

Some people prefer to always check the profit, even when updating the minimum:

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

This does the same thing in fewer lines. When price is the new minimum, price - min_price is 0, which never beats a positive max_profit. Both versions are correct.

Complexity analysis

Time: O(n). We visit each price exactly once. Each visit does O(1) work (a comparison and possibly an update). Total: O(n).

Space: O(1). We use two variables (min_price and max_profit) regardless of input size. No extra arrays, no hash maps, no stacks.

This is as good as it gets for this problem. You have to look at every price at least once (you cannot know the answer without seeing all the data), so O(n) time is optimal. And O(1) space means you are not using any memory beyond the input.

Why the greedy approach works here

Not every problem can be solved greedily. Greedy works when the optimal solution can be built from locally optimal choices. Here, that holds because:

• You must buy before you sell (the problem has a left-to-right ordering constraint).
• For any sell day, the best buy day is the minimum price to its left.
• By tracking the running minimum, you know the best buy price for every possible sell day without any extra computation.

There is no case where picking a higher buy price leads to a better outcome. The running minimum always gives you the best possible buy point for any future sell day.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• Decreasing prices like [5, 4, 3, 2, 1]: no profitable trade exists, return 0.
• All same prices like [3, 3, 3, 3]: profit is always 0.
• Single element [5]: no trade possible, return 0.
• Two elements [1, 5]: profit is 4. [5, 1]: profit is 0.
• Minimum at the very end like [5, 3, 1]: the minimum never gets a chance to be a buy day for a later sell.

The one-pass solution handles all of these correctly without special cases.

The building blocks

This problem is built on a single reusable pattern: running min/max. The idea is simple. As you iterate through a sequence, maintain the minimum (or maximum) value seen so far. This lets you answer "what is the best value to my left?" in O(1) at every position.

The running minimum pattern shows up in many other problems:

• Trapping Rain Water: track running max from left and right to find water level at each position.
• Maximum Subarray (Kadane's): a close cousin that tracks the running maximum subarray sum.
• Largest Rectangle in Histogram: uses running min heights to determine bar boundaries.

Once you internalize this pattern as a building block, you stop thinking of LeetCode Buy Sell Stock as a standalone problem. It becomes "running min with a profit check." And when you see Trapping Rain Water, you think "running max from both sides." Same brick, different wall.

From understanding to recall

You have read through the one pass solution and it makes sense. But here is the thing: understanding a solution is very different from being able to produce it from scratch. In an interview, nobody shows you the solution and asks if you understand it. You have to write it yourself, from memory, under time pressure.

Spaced repetition is built to close this gap. Instead of solving this problem once and moving on (and forgetting it in two weeks), you revisit the core pattern at increasing intervals. Each time you write the running minimum logic from scratch. After a few repetitions, it is permanent.

The running minimum is one of roughly 60 reusable building blocks that show up across hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a much better strategy than grinding through problems one by one and hoping they stick.

Related posts

• The Sliding Window Pattern - Another single-pass technique for subarray and substring problems
• Hash Map Patterns - Complement lookup is the building block behind Two Sum, a natural companion to this problem
• The Two Pointers Pattern - More single-pass strategies for array problems