Leetcode - Best Time to Buy and Sell Stock Solution

Choose one purchase day and one later sale day to get the largest positive price difference. My first solution checked every pair, which was O(n²). Tracking the lowest price seen so far reduces the scan to O(n).

The single transaction constraint

The input is an array prices, where prices[i] is the price on day i. I may buy once and sell once later, so the sell day must come after the buy day. A falling sequence produces no profit, and an empty or single day input also returns zero.

My initial thought was to check every possible pair of buy and sell days:

function maxProfitNaive(prices) {
  let maxProfit = 0;

  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const profit = prices[j] - prices[i];
      if (profit > maxProfit) {
        maxProfit = profit;
      }
    }
  }

  return maxProfit;
}

The pairwise method is correct, but its O(n²) running time grows quickly with the number of days.

One pass and its invariant

I then tracked the minimum price seen so far and the best profit found at each day. The current price is the possible selling price, while minPrice represents the best legal buying price before it.

function maxProfit(prices) {
  let minPrice = Infinity; // Track the lowest price seen so far
  let maxProfit = 0; // Track the maximum profit found

  for (let i = 0; i < prices.length; i++) {
    // If current price is lower, update our minimum
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    }
    // Otherwise, check if selling now gives better profit
    else if (prices[i] - minPrice > maxProfit) {
      maxProfit = prices[i] - minPrice;
    }
  }

  return maxProfit;
}

After day i, minPrice contains the smallest price in days 0 through i. The value of maxProfit is the best valid profit for those days. If the current price is lower, the algorithm updates minPrice for future sales. Otherwise, prices[i] - minPrice gives the best profit from a sale today. The value of maxProfit preserves the best result from earlier days.

Trace, Java implementation, and complexity

For [7, 1, 5, 3, 6, 4], the one pass state changes as follows:

const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5

The trace is:

• Day 0: price is 7, minPrice becomes 7, profit is 0
• Day 1: price is 1, minPrice becomes 1 (lower!), profit is still 0
• Day 2: price is 5, minPrice is 1, profit = 5 - 1 = 4
• Day 3: price is 3, minPrice is 1, profit = 3 - 1 = 2 (not better)
• Day 4: price is 6, minPrice is 1, profit = 6 - 1 = 5 (better!)
• Day 5: price is 4, minPrice is 1, profit = 4 - 1 = 3 (not better)

The best profit is 5, from buying at 1 and selling at 6.

The Java version keeps the same invariant:

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

My first pairwise solution was intuitive, but it tracked more information than necessary. The one pass version uses O(n) time and O(1) extra space. It also handles a decreasing array because maxProfit remains zero while minPrice keeps moving down.

The main question is what state makes each future decision possible. Here, the minimum price and maximum profit are enough, so the pairwise search is unnecessary.