Fresher · Arrays & hashing

Best Single Buy and Sell

Return the maximum profit from buying once and selling on a later day. Return 0 if no positive profit exists. Prices are nonnegative integers; leave the input unchanged.

Examples

[7, 1, 5, 3, 6, 4] → 5

Compare approaches

Every legal trade

Compare every earlier buy with every later sell.

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

function maxProfit(prices) { let best = 0; for (let i = 0; i < prices.length; i++) for (let j = i + 1; j < prices.length; j++) best = Math.max(best, prices[j] - prices[i]); return best; }

Minimum price so far

For each selling day, the cheapest earlier purchase is the only candidate needed.

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

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

Common traps

Sorting loses chronological order.
A sale must follow its purchase.

Practise in the workspace →