#121 Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy and a single day to sell. Return the maximum profit you can achieve. Test.

Intuition

As we scan left to right, we track the lowest price we've seen. At each position, the best profit we could get by selling today is prices[i] - minPrice. We keep a running maximum of this value.

Approach (Greedy)

1. Initialize minPrice to the first price and maxProfit to 0.
2. For each subsequent price, update minPrice if the current price is lower.
3. Otherwise, compute profit and update maxProfit if it's higher.
4. Return maxProfit.

Solution

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

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

  return maxProfit;
}

Complexity Analysis