Best Time to Buy and Sell Stock

Approach Summary

Track running minimum price. At each day, profit = price - min_so_far. Track max profit seen.

Full Solution & Approach

The naive solution compares every buy price with every later sell price and is O(n²). The insight that makes this O(n): the best profit achievable when selling on day i depends only on the cheapest price seen before day i. So scan the array once, tracking two values — the minimum price seen so far and the best profit so far. For each price, first update the running minimum, then compute the profit if you bought at that minimum and sold at the current price, and keep the larger of the running best and this new candidate. Because you are always free to buy at any earlier price and sell at any later price, considering the cheapest earlier price is never worse than any other earlier price. The first day cannot be a sale (there is no earlier buy), but the formula handles it naturally since the minimum updates to prices[0] before the first profit is computed, giving profit 0. The problem allows only one transaction, so the single-pass min-tracking is both minimal and optimal.

One pass over n prices with constant work per element — O(n) time. Only two scalar variables are kept, so O(1) space.

Solution Code

Solution

def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

function maxProfit(prices) {
  let minPrice = Infinity;
  let best = 0;
  for (const p of prices) {
    minPrice = Math.min(minPrice, p);
    best = Math.max(best, p - minPrice);
  }
  return best;
}

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        best = Math.max(best, p - minPrice);
    }
    return best;
}

int maxProfit(const vector<int>& prices) {
    int minPrice = INT_MAX;
    int best = 0;
    for (int p : prices) {
        minPrice = min(minPrice, p);
        best = max(best, p - minPrice);
    }
    return best;
}

Edge Cases to Watch

Strictly decreasing prices — best stays 0 (no profitable transaction)
Single price — no transaction possible, return 0
Constant prices — profit 0
Best transaction ends on the last day — captured because every day is evaluated

How to Recognize This Pattern

Single buy and sell, maximize profit
Track min seen so far — greedy O(n)

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)