Problem: Write a function that takes an array of stock prices and returns the best profit you could make from one purchase and one sale.

For example:

const prices = [10, 6, 3, 9, 11, 5];

maxProfit(prices);
// returns 8 (buying for $3 and selling for $11)

Brute Force Solution

Try every pair of times treating the earlier time as buy time and the later time as sell time, and see which one is higher.

// O(n^2) time
function maxProfit(prices) {
  let maxProfit = 0;
  for (let i=0; i < prices.length; i++) {
    for (let j=0; j < prices.length; j++) {
      let earlierTime = Math.min(i, j);
      let laterTime = Math.max(i, j);

      let earlierPrice = prices[earlierTime];
      let laterPrice = prices[laterTime];

      let potentialProfit = laterPrice - earlierPrice;

      maxProfit = Math.max(maxProfit, potentialProfit);
    }
  }
  return maxProfit;
}

One problem: you can never have a negative profit!

Better Solution

We have to compare every price so O(n) is the best we can do. Let’s take a greedy approach by keeping a running maxProfit until the end. So for every price check if:

  • we can get a better profit by buying at minPrice and selling at currentPrice
  • we can have a new minPrice

Initialize maxProfit as the first profit we could get, not 0.

// O(n) time & O(1) space
function maxProfit(prices) {
  let minPrice = prices[0];
  let maxProfit = prices[1] - prices[0];

  for (let i = 1; i < prices.length; i++) {
    let currentPrice = prices[i];
    let potentialProfit = currentPrice - minPrice;
    maxProfit = Math.max(maxProfit, potentialProfit);
    minPrice = Math.min(minPrice, currentPrice);
  }

  return maxProfit;
}