LeetCode 121. Best Time to Buy and Sell Stock

This post was migrated from Tistory. You can find the original here.

Problem

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

I set up variables for the low point (buy) and high point (sell), but the only approach I could come up with was O(n^2), so I went and checked the discussion.

When the low point changes,

1. If a high point comes after the (new) low point in time, the previous low point can never yield a bigger profit.

2. If a high point occurred before the (new) low point, keep track of the profit from the previous low/high pair. Then, since the high point must come after the low point, reset the high point to coincide with the new low point.

Once you settle on point 1, the rest of the logic seems to follow naturally.

    def maxProfit(self, prices: List[int]) -> int:
        buy, sell, profit = prices[0], prices[0], 0
        for i in range(1, len(prices)):
            val = prices[i]
            if val < buy:
                profit = max(profit, sell - buy)
                buy = val
                sell = val
            elif val > sell and val > buy:
                sell = val

        return max(profit, sell-buy)