Problem can be found in here!
Solution 1: Left Right Pointer
def maxProfit(prices: List[int]) -> int:
maxGap = 0
left, right = 0, 1
while right < len(prices):
if prices[left] < prices[right]:
maxGap = max(maxGap, prices[right] - prices[left])
right += 1
else:
left, right = right, right + 1
return maxGapTime Complexity: , Space Complexity:
Explanation: We cannot buy a stock in the future and sell it now in stock market; thus, we only need to store the lowest stock price in every iteration. And in next iteration, we only need to check whether current stock price is higher than previous lowest stock price. If so, then we might need to update maxGap. On the other hand, if current stock price is lower than previous lowest price, then we need to update two pointers (left, right).
Solution 2: Min Max
def maxProfit(prices: List[int]) -> int:
buyPrice, maxGap = float("inf"), 0
for price in prices:
buyPrice, maxGap = min(buyPrice, price), max(maxGap, price - buyPrice)
return maxGapTime Complexity: , Space Complexity:
Explanation: Instead of using two variables to store the index of the lowest and current price of stock like solution 1, we only need to store the lowest price as iteration goes on. If we find current price is less than pervious lowest price, then it is possible that the maximum profit might change. Therefore, we might need to update the value of maxGap as shown in the code section above.