Question

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 one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

My Solution

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let profit = 0
  let cheapest = prices[0]
  for (i = 1; i < prices.length; i++) {
      if (prices[i] < cheapest) {
          cheapest = prices[i]
      } else {
          if (profit < (prices[i] - cheapest)){
              profit = (prices[i] - cheapest);
          }
      }
  }
  return profit
};

Key Takeaways

To be honest, my first attempt at solving this problem resulted in an O(n2)O(n^2)O(n2) solution, which failed to handle larger datasets efficiently. Later, I came across an optimized approach that is often referred to as the "sliding window" technique.

Sliding Window Technique

The solution I used can be categorized as a sliding window approach. Sliding window is a common algorithmic technique where a "window" (a subset of the data) is moved along the input to examine different parts of the dataset while maintaining efficiency. In this problem, the "window" is represented by tracking the minimum price so far (the start of the window) and comparing it to the current price (the end of the window) to calculate potential profit.

Why This Solution Is Greedy

At the same time, this solution also demonstrates a greedy algorithm because:

1. It makes a series of locally optimal choices: at each step, it tries to minimize the purchase price and maximize the profit based on the current data.
2. These local choices eventually lead to the globally optimal result: the maximum profit possible.