Best Time to Buy and Sell StockEasy

Given an array of daily stock prices, choose one day to buy and a later day to sell to maximize profit. Return 0 if no profit is possible.

Examples

Input: prices = [7,1,5,3,6,4] → Output: 5 (buy at 1, sell at 6)

Input: prices = [7,6,4,3,1] → Output: 0 (prices only fall)

Approach

Checking every buy/sell pair is O(n²). One pass is enough: walk the prices while tracking the lowest price seen so far. At each day, the best possible profit if you sold today is today's price minus that running minimum — you never need to re-check earlier days individually, because the running minimum already summarizes the best possible buy point up to now.

Complexity — best & worst case

Brute force — time O(n²)

Optimal — time O(n), best and worst case are the same — always one full pass

Optimal — space O(1)

Code

// You're given an array of daily stock prices. Choose one day to buy
// and a later day to sell to maximize profit. Return 0 if no profit
// is possible.

// --- Brute force: try every buy/sell pair ---
function maxProfitBrute(prices) {
  let max = 0;
  for (let buy = 0; buy < prices.length; buy++) {
    for (let sell = buy + 1; sell < prices.length; sell++) {
      max = Math.max(max, prices[sell] - prices[buy]);
    }
  }
  return max;
}

// --- Optimal: one pass, track the lowest price seen so far ---
// At each day, the best possible sell is "today's price minus the
// cheapest day before it" — no need to check every earlier day again.
function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
}

// --- Example Usage ---
console.log(maxProfit([7, 1, 5, 3, 6, 4]));      // 5 (buy at 1, sell at 6)
console.log(maxProfitBrute([7, 1, 5, 3, 6, 4])); // 5
console.log(maxProfit([7, 6, 4, 3, 1]));         // 0 (prices only fall)