LeetCode Best Time to Buy and Sell Stock: One-Pass O(n)

Beginner 8 min read

What you'll learn

✓Brute-force approach and its complexity
✓Optimal approach with intuition
✓Edge cases that trip people up
✓How to talk through it in an interview
✓Related LeetCode problems to follow up with

Prerequisites

•Basics from arrays introduction and Big O notation

Best Time to Buy and Sell Stock is LeetCode problem 121, rated Easy. It looks like a trick question the first time you see it, then becomes a one-liner once you see the pattern. The lesson it teaches, tracking a running extreme while sweeping the array, comes up constantly.

The Problem

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximize profit by choosing a single day to buy and a different later day to sell. Return the maximum profit; if no profit is possible, return 0.

Example:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price 1) and sell on day 5 (price 6).

Buying after selling is not allowed, which is the only real constraint.

Brute Force

Try every pair where the buy day comes before the sell day.

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

Time: O(n^2). Space: O(1). For LeetCode constraints up to n = 10^5, this will time out hard.

Optimal Solution

The key insight: at each day i, the best sell price is just prices[i], and the best profit you could achieve by selling today is prices[i] - min(prices[0..i-1]). So we only need to track the minimum price seen so far.

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    best = 0
    for price in prices[1:]:
        best = max(best, price - min_price)
        min_price = min(min_price, price)
    return best

Line by line:

Guard against an empty array.
min_price is the cheapest day we have seen so far. Start with day 0.
best is the answer we are building up.
For each subsequent day, the profit if we sold today is price - min_price. Update best if that beats it.
Then update min_price for future iterations.

Order matters. Compute the candidate profit before updating min_price, otherwise you would be selling and buying on the same day.

Walk Through an Example

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

Start: min_price = 7, best = 0.
Day 1, price 1. Profit if sell = 1 - 7 = -6. best stays 0. Update min_price to 1.
Day 2, price 5. Profit = 5 - 1 = 4. best becomes 4. min_price stays 1.
Day 3, price 3. Profit = 3 - 1 = 2. best stays 4.
Day 4, price 6. Profit = 6 - 1 = 5. best becomes 5.
Day 5, price 4. Profit = 4 - 1 = 3. best stays 5.

Return 5.

Edge Cases

Strictly decreasing prices like [7, 6, 4, 3, 1]. No profitable trade exists. Return 0.
Single-element array. No trade possible. Return 0.
Empty array. Defensive check at the top.
All equal prices. Profit is 0.
Integer overflow. Not a Python concern, but in C++ or Java you should think about it.

Complexity Analysis

Time: O(n). One pass.
Space: O(1). Two scalars regardless of input size.

This is as efficient as the problem allows; you must look at every price at least once.

How to Explain It in an Interview

Restate the problem and confirm: you can only buy once and sell once, and sell day must come after buy day.
Mention the brute force in one sentence to anchor complexity.
Explain the key insight: “For each day, I only care about the minimum I have seen so far. The best profit ending at this day is price minus running min.”
Code it and emphasize the order: compute profit first, then update min.
State O(n) time and O(1) space.
Mention the multi-transaction variant 122 if asked for an extension.

For the array fundamentals that make this trivial, see arrays common operations.

Wrap up

The pattern here, “sweep once, maintain a running extreme, derive the answer at each step”, is one of the most reusable ideas in array problems. Maximum Subarray uses the same skeleton with a running sum instead of a running min. Master it on this problem and a dozen others fall out for free.