Best Time to Buy and Sell Stock Solution

Problem

Given an array of daily stock prices, find the maximum profit from a single buy followed by a single sell. You must buy before you sell; if no profitable trade exists, return 0.

Example:

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

Counter-example: With prices = [7, 6, 4, 3, 1], prices only fall — no profitable trade exists, so return 0.

Intuition

The optimal buy day is always the cheapest price seen before the current day. Scanning left to right while tracking the running minimum lets you compute "best profit if I sell today" in constant time at each step, turning a nested search into a single pass.

Approach 1 — Brute Force

Try every valid buy-sell pair (buy index before sell index) and return the highest profit found.

Steps:

Initialize max_profit = 0.
For each buy_idx from 0 to n − 2.
For each sell_idx from buy_idx + 1 to n − 1.
Compute profit = prices[sell_idx] - prices[buy_idx].
Update max_profit if profit is larger.
Return max_profit.

1def maxProfit(prices: List[int]) -> int:
2    max_profit = 0
3    for buy_idx in range(len(prices)):
4        for sell_idx in range(buy_idx + 1, len(prices)):
5            profit = prices[sell_idx] - prices[buy_idx]
6            max_profit = max(max_profit, profit)
7    return max_profit

Time: O(n²) — every pair of buy and sell days is checked once
Space: O(1) — only two integer variables are needed

Approach 2 — One-Pass Minimum Tracking

Scan once, keeping track of the cheapest price seen so far. At each step, the best possible profit if selling today is price - min_price.

Steps:

Initialize min_price = infinity and max_profit = 0.
For each price in prices:
Update min_price to the smaller of min_price and price.
Compute profit = price - min_price and update max_profit if larger.
Return max_profit.

1def maxProfit(prices: List[int]) -> int:
2    min_price = float('inf')
3    max_profit = 0
4    for price in prices:
5        min_price = min(min_price, price)               # track cheapest buy day seen so far
6        max_profit = max(max_profit, price - min_price)
7    return max_profit

Time: O(n) — single pass through the array
Space: O(1) — two variables regardless of input size

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only to understand the problem structure; never acceptable in interviews
One-Pass Min Tracking	O(n)	O(1)	Always — optimal for all inputs

Common Mistakes

Initializing max_profit to -1 or -infinity — when all prices fall (e.g., [7, 5, 3]), the correct answer is 0 (don't trade). A negative initialization forces a losing trade into the result.
Starting the inner brute-force loop at buy_idx instead of buy_idx + 1 — allows buying and selling on the same day; the profit is always 0 so the final answer is unchanged here, but the identical bug silently breaks harder variants like Stock III.
Confusing this with "Best Time to Buy and Sell Stock II" — summing every consecutive daily gain is optimal for unlimited transactions but overstates profit here, where only one buy-sell pair is allowed.
Sorting the array to find the global minimum and maximum — this destroys the temporal ordering; you must buy before you sell, and the global minimum might appear after the global maximum in the original array.
Applying this one-pass pattern to multi-transaction variants — tracking a single running minimum breaks down once two or more transactions are allowed; those variants require DP over a "transactions remaining" state dimension.

Best Time to Buy and Sell Stock — Solution