JavaScript - Best Time to Buy and Sell Stock [Written Explanation + Code]
Table of Contents:\n High level overview of the problem\n Translate words to solution\n Code demo\n\n## High level overview of the problem:\n\nYou are given an 
# Table of Contents:\n* High level overview of the problem\n* Translate words to solution\n* Code demo\n\n## **High level overview of the problem:**\n\n*You are given an array prices where prices[i] is the price of a given stock on the ith day.*\n\n*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.*\n\n*Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.*\n\nWhen it comes to buying stocks in real life, you want to buy low and sell high. The concept is applied in this problem. We need to keep track of two prices in order to get a positive profit.\n\n**There are 2 ways to solve this problem:**\n1. Brute Force\n2. Greedy Algorithm\n\n## **Translate words to solution:**\n\n**Solution #1 Brute Force:**\n\nIf we iterate over the array with one for loop (buy price), we need an additional for loop (sell price) to scan the elements to the right of it. The reason we need a second for loop is because we need the buy price from the first for loop so that we can subtract the sell price in the second for loop. If we can loop over the elements with two for loops then we can generate the combinations to achieve a maximum profit. \n\nTime Complexity: O(n^2)\nSpace Complexity: O(1)\n\n**Solution #2 Greedy Algorithm:**\n\nThe idea of the greedy algorithm is keep track of the locally optimal solution that will eventually build up to an optimal global solution. \n\nIn order for us to get a locally optimal solution we need to keep track of the minimum buy price, the maximum sell price, and the current profit. The formula for getting the current profit is equal to buy price subtracted by the sell price.\n\nOn every iteration, we simultaneously check if the current profit is greater than the global profit, if it is then we update the global profit to equal our current profit. \n\nTime Complexity: O(n)\nSpace Complexity: O(1)\n## **Code demo:**\n\n**Solution #1 Brute Force:**\n\n```\nfunction maxProfit(prices) {\n  let globalProfit = 0;\n\t// the reason prices.length - 1 is because we are using the second for loop to scan every element to the right of i\n  for (let i = 0; i < prices.length - 1; i++) {\n\t  // the reason j is i + 1 is because we are scanning all the combinations of the first for loop\n    for (let j = i + 1; j < prices.length; j++) {\n      const currentProfit = prices[j] - prices[i]\n\n      if (currentProfit > globalProfit) {\n        globalProfit = currentProfit\n      }\n    }\n  }\n\n  return globalProfit;\n}\n\n```\n\n**Solution #2 Greedy Algorithm:**\n\n```\nfunction maxProfit(prices) {\n  let globalProfit = 0;\n  // minBuyPrice is set to Infinity because we can guarantee the first element will be set to the buy price \n  let minBuyPrice = Infinity;\n\n  for (let i = 0; i < prices.length; i++) {\n    if (minBuyPrice > prices[i]) {\n      minBuyPrice = prices[i];\n    }\n\n    const currentProfit = prices[i] - minBuyPrice;\n\n    if (currentProfit > globalProfit) {\n      globalProfit = currentProfit;\n    }\n  }\n\n  return globalProfit;\n}\n```
['JavaScript']