Leetcode problem 19 - Best Time to Buy and Sell Stock

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.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  // Initialize the profit to 0
  let profit = 0;
  // Initialize the minimum price to the first element of the prices array
  let min = prices[0];

  // Loop through the prices array starting from the second element
  for (let i = 1; i < prices.length; ++i) {
    // If the current price is less than the minimum price so far
    if (min > prices[i]) {
      // Update the minimum price
      min = prices[i];
      // If the difference between the current price and the minimum price is greater than the current profit
    } else if (prices[i] - min > profit) {
      // Update the profit
      profit = prices[i] - min;
    }
  }
  // Return the maximum profit
  return profit;
};

Inside the loop, it checks if the current element prices[i] is less than the current min. If it is, then update the min to the current prices[i], as we have found a new minimum price.

If the current prices[i] is not less than min, it means that there is a possibility of making a profit. So, it calculates the potential profit by subtracting the min from the current prices[i] (i.e., prices[i] - min).

If the potential profit is greater than the current profit, update the profit to the potential profit. This step ensures that profit always holds the maximum profit achieved so far.

The loop continues iterating through the prices array, updating min and profit accordingly.

After the loop finishes, the function returns the value of profit, which holds the maximum profit that can be achieved by buying and selling the stock.

The time complexity of this algorithm is O(n), where n is the length of the prices array. The algorithm iterates through the prices array once, so the time complexity is linear with respect to the size of the input.