LeetCode #121. Best Time to Buy and Sell Stock with JavaScript

Solutions to LeetCode's 121. Best Time to Buy and Sell Stock with JavaScript.

Solution 1

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

• Time complexity: O(n^2)
• Space complexity: O(1)

The Time complexity of this solution is O(n^2), so I'll find another solution.

Solution 2

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  let maxProfit = 0;
  let stockToBuy = prices[0];

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

    if (maxProfit < profit) {
      maxProfit = profit;
    }
  }
  return maxProfit;
};

• Time complexity: O(n)
• Space complexity: O(1)

I was able to change the for loop to one and shorten the time complexity to O(n).