Comprehensive Python Solution – Thought Process & Examples
Approach\nYour first thought when approaching this problem is probably that we should buy on the cheapest day and then sell on the most expensive day. This work
**Approach**\nYour first thought when approaching this problem is probably that we should buy on the cheapest day and then sell on the most expensive day. This works for cases such as ```[1,4,3,2,5]```  where the highest priced day is after the lowest priced day (in this case you can buy on day ```0``` and sell on day ```4``` to make a profit of ```4```. However, in a case such as example 1, ```[7,1,5,3,6,4]```, this method would assert that we can get a profit of ```6``` by selling at the highest price, ```7```, and buying at the lowest price, ```1```. Unfortuantely, this is not possible since we need to buy before we sell! So, how can we go from here? Well, let\'s think about this major restriction \u2013 we need to sell *after* we buy. This means that we can figure out the maximum profit to make by going to each day and seeing what would happen if we buy on that day and sell later!\n\n**Method 1: Brute-force; Time: O(N^2), Space: O(1) \u2014> TLE**\n```\ndef maxProfit(self, prices: List[int]) -> int:\n        profit = 0 #best profit possible\n        for i in range(len(prices)-1):\n            buy = prices[i] #assume we buy today\n            sell = max(prices[i+1:]) #we sell on the future day with the highest price\n            if sell-buy > profit: #if this combination improves our profit\n                profit = sell-buy #update the profit\n        return profit\n```\nIn this method we iterate through all the days and then figure out the highest profit we can make by buying on day ```i``` and selling on the day with the maximum price that occurs after this day (day ```i+1``` or later). Each time we check to see if this improved our profit. This method has a time complexity of ```O(N^2)``` since for every day ```i```, we need to look at ```N-i-1``` days afterwards to find the best day to sell. Unfortunately this results in a time limit exception since some of the leetcode test cases are super lengthy, so we will need to find a better solution.\n\n**How to improve - what to do when stuck**\nFirst, let\'s identify what step in our process is slowing down the code. It isn\'t figuring out which day to buy, since we just assume we buy on day ```i```, but finding the day we sell on. Since the day we sell on is in the future, we need to look at every day even though we sometimes already looked at them in the last iteration of our ```for``` loop. So, let\'s brainstorm how we can improve this method. Rather than assuming we buy on day ```i```, let\'s assume we actually sell on day ```i```. Since we have already looked at the ```i-1``` days before this day, we can keep track of the cheapest day to buy on which was before day ```i```. This will greatly improve the speed of our code since we don\'t need to look at a ton of days each time!\n\n**Method 2: One-pass; Time: O(N), Space: O(1)**\n```\ndef maxProfit(self, prices: List[int]) -> int:\n        profit = 0 #our answer\n        buy = prices[0] #the day we buy on\n        for i in range(1,len(prices)):\n            sell = prices[i] #assume we sell today\n            profit = max(profit,sell-buy) #update the maximum profit if we were to sell today\n            buy = min(buy,prices[i]) #update the cheapest price we could buy\n        return profit\n```\nAs mentioned before, in this method we keep track of the cheapest day to buy, then see what would happen if we sold our stock on day ```i```. First we see if the profit we make from selling today is better than the profit we previously could make. Then make sure that this value, ```buy``` is as small as possible by checking to see if the current price is cheaper. To help illustrate how this works, I will walk through both examples provided with the question.\n\n**Example 1:**\n```\nprices = [7,1,5,3,6,4]\n\ni = 1, previous max profit = 0, buy = 7, sell = 1\ni = 2, previous max profit = 0, buy = 1, sell = 5\ni = 3, previous max profit = 4, buy = 1, sell = 3\ni = 4, previous max profit = 4, buy = 1, sell = 6\ni = 5, previous max profit = 5, buy = 1, sell = 4\n```\n\n**Example 2:**\n```\nprices = [7,1,5,3,6,4]\n\ni = 1, previous max profit = 0, buy = 7, sell = 6\ni = 2, previous max profit = 0, buy = 6, sell = 4\ni = 3, previous max profit = 0, buy = 4, sell = 3\ni = 4, previous max profit = 0, buy = 3, sell = 1\n```\n\nI hope that walking through these examples has helped you understand what\'s going on! If you still have any questions, please comment and I will try to help!\n\n**Thanks for Reading!**\nIf this post has been helpful, please consider upvoting! Also, if I made any mistakes or there are other optimizations, methods I didn\'t consider, etc. please let me know!\n\n\n
['Python']