Best Time to Buy and Sell Stock

Examples

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

Buy on day 1 (price 1) and sell on day 4 (price 6). Profit = 6 - 1 = 5.

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

Prices only ever go down, so no trade makes a profit — best to not trade at all.

Input: prices = [2, 4, 1]
Output: 2

Buy on day 0 (price 2) and sell on day 1 (price 4). Profit = 2. Buying on day 2 is too late to sell for a profit.

Constraints

• 1 <= prices.length <= 10^5

• 0 <= prices[i] <= 10^4

Approach

The brute-force idea is to try every possible pair of a buy day and a later sell day, compute the profit for each pair, and keep the best one. That checks every pair, which is a lot of repeated work.

A much faster approach scans the prices once, left to right, while keeping track of two things: the lowest price seen so far, and the best profit found so far. On each day, you first check "if I sold today, having bought at the cheapest price I've seen, what would my profit be?" and update the best profit if that's better. Then you update the lowest price if today's price is even lower. By the end of one pass, you've considered every valid buy-then-sell pair without ever looking backwards.

Solutions

Brute Force — Every Buy/Sell Pair

Try every day as a potential buy day, and every later day as a potential sell day, tracking the best profit seen. Correct, but it re-examines the same days over and over.

function maxProfit(prices) {
  let best = 0;

  for (let buy = 0; buy < prices.length; buy++) {
    for (let sell = buy + 1; sell < prices.length; sell++) {
      const profit = prices[sell] - prices[buy];
      if (profit > best) {
        best = profit;
      }
    }
  }

  return best;
}

Time: O(n²) · Space: O(1)

Optimal — Track the Running Minimum

Walk through the prices once. Keep the lowest price seen so far as the best possible buy point, and at each day check what profit selling today would give against that minimum, updating the best answer as you go.

function maxProfit(prices) {
  let minPrice = Infinity;
  let best = 0;

  for (const price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else if (price - minPrice > best) {
      best = price - minPrice;
    }
  }

  return best;
}

Time: O(n) · Space: O(1)