0121. Best Time to Buy and Sell Stock

Problem Category:: Sliding window methods Neetcode Category:: Sliding window

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

• You are given an array prices where prices[i] is the price of a given stock on the ith day
• 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.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Optimal

Sliding window simplified

• Max profit always depends on the minimum encountered price
• Traverse through the list (one-pass) and keep updating lowest and max_profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        lowest = prices[0]
        for price in prices:
            if price < lowest:
                lowest = price
            res = max(res, price - lowest)
        return res

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

Sliding window

Use Sliding window methods

• Contraction condition is when prices[l] < prices[r] since at that point, r is a lower price and can provide better profits than the current l for any windows to the right

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        l, r = 0, 1
        # Iterate through sliding window
        while r < len(prices):
            # Contraction condition (buy price > sell, reached maximum expansion for this l)
            if prices[l] > prices[r]:
                l = r
            else:
                # Process window
                if prices[r] - prices[l] > max_profit:
                    max_profit = prices[r] - prices[l]
            # Expand window
            r += 1
        return max_profit

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