Best Time to Buy and Sell Stock: From Brute Force to One-Pass O(n)

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit from a single transaction — buy on one day, sell on a later day. If no profit is possible (prices only decrease), return 0.

Constraints:

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴

Examples from the prompt:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 6 - 1 = 5.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0

No transaction yields profit — prices only go down.

Initial Intuition — Brute Force

First thought: try every possible buy-sell pair.

func maxProfit(prices []int) int {
    maxProfit := 0
    n := len(prices)
    for buy := 0; buy < n; buy++ {
        for sell := buy + 1; sell < n; sell++ {
            profit := prices[sell] - prices[buy]
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }
    return maxProfit
}

Straightforward logic: for each buy day, try every sell day after it. Compute profit, track the maximum.

Complexity: O(n²) — full nested loop. For n = 10⁵, this runs ~10¹⁰ iterations. Won't pass.

Key Observation

Re-examine the example: [7, 1, 5, 3, 6, 4]

For any candidate sell day, maximum profit comes from buying at the lowest price seen before that day.

Maximum profit: max(0, 4, 2, 5, 3) = 5. Matches expected output.

Pattern: Track Minimum While Scanning

From the table above, we realize: no nested loop needed. Just one pass left to right, maintaining two values:

1. Lowest price seen so far (min_price)
2. Maximum profit achievable if selling at the current price (max_profit)

At each step i:

• Profit if sell now = prices[i] - min_price
• Update max_profit if this profit is larger
• Update min_price if prices[i] is smaller than min_price

Optimal Solution — One-Pass O(n)

func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0

    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else {
            profit := price - minPrice
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }

    return maxProfit
}

Or a more concise version:

func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0

    for _, price := range prices {
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price-minPrice)
    }

    return maxProfit
}

What about the no-profit case? If prices only decrease (example 2: [7, 6, 4, 3, 1]), then price - min_price is always negative. But max_profit starts at 0, and max(0, negative) = 0. So it returns 0 — matching the requirement.

Visualization

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

i=0: price=7  → min_price=7    profit=N/A   max_profit=0
i=1: price=1  → min_price=1    profit=N/A   max_profit=0
i=2: price=5  → min_price=1    profit=4     max_profit=4  ✓
i=3: price=3  → min_price=1    profit=2     max_profit=4
i=4: price=6  → min_price=1    profit=5     max_profit=5  ✓ (new max!)
i=5: price=4  → min_price=1    profit=3     max_profit=5

Return 5

Complexity

For n = 10⁵, this solution completes in <1ms in any language.

Why This Pattern Matters

The "track minimum from the left while scanning" pattern is a building block for many problem variants:

• Best Time to Buy and Sell Stock II — unlimited transactions allowed
• Best Time to Buy and Sell Stock III — at most two transactions
• Trapping Rain Water — track max from left and right
• Maximum Subarray (Kadane) — track current_sum and max_sum

All stem from the same idea: maintain optimal state from data already passed, update state as you move forward.

Key Takeaway

Best profit comes from buying at the lowest price seen so far and selling at the current price. Track both in one pass.

This problem teaches that brute force can crumble with a single simple observation. Always ask before writing a nested loop: "What do I actually need to remember from the data I've already seen?"