[LeetCode/Python] 121. Best Time to Buy and Sell Stock

📌 Problem

[LeetCode] 121. Best Time to Buy and Sell Stock

📌 Solution

1: Dynamic Programming

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0

        opt = [0] * n
        min_val = prices[0]
        
        # opt[i] = max profit achievable up to day i
        for i in range(1, n):
            if prices[i] < min_val:
                min_val = prices[i]
                opt[i] = opt[i-1]
            else:
                opt[i] = max(opt[i-1], prices[i] - min_val)
        return opt[n-1]

• Time Complexity: O(n) → iterate through prices once
• Space Complexity: O(n) → extra array opt to store profit up to each day

2. Linear Scan ⭐️

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)

        return max_profit

• Time Complexity: O(n) → still one pass through the array
• Space Complexity: O(1) → only two variables (min_price, max_profit)