Best Time to Buy and Sell Stock

EasySliding WindowArraySliding WindowDynamic Programming

Problem

You are given an array of daily stock prices. Choose a single day to buy and a later day to sell so as to maximize profit, and return that maximum profit. If no ordering of buy and sell days produces a gain, return zero rather than a loss.

Example. For [7, 1, 5, 3, 6, 4], buying on the day priced 1 and selling on the day priced 6 yields the best profit of 5.

Key idea

Checking every buy-sell pair directly costs O(n²). The improvement comes from noticing that for any fixed sell day, the best possible buy day is always the cheapest price that occurred at or before it: there is never a reason to consider a more expensive earlier day. That means a single left-to-right pass suffices: keep a running minimum price seen so far, treat it as a window boundary that only ever moves forward to a lower point, and at each day compute the profit from selling at today's price against that running minimum. Update the best profit whenever this beats the current best, and update the running minimum whenever today's price is lower still.

Solution

function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let bestProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price); // lowest price seen so far (candidate buy day)
    bestProfit = Math.max(bestProfit, price - minPrice); // profit if sold today
  }

  return bestProfit;
}

Complexity

  • Time: O(n). One pass through the prices.
  • Space: O(1). Only the running minimum and best profit are tracked.

Watch out for

  • The buy day must come before the sell day; tracking the minimum-so-far rather than the global minimum enforces this automatically.
  • Return 0, not a negative number, when prices only ever decrease.
  • This problem allows exactly one buy and one sell; a variant that permits multiple transactions needs a different approach entirely.

Pattern

This is the simplest form of a single-pass running-extremum window: the window's low edge jumps forward to a new minimum whenever one appears, while the current price plays the role of the window's other edge. The same instinct (carry one running summary forward instead of rescanning) underlies later, more elaborate sliding-window problems.

Related questions