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

📌 Problem

[LeetCode] 122. Best Time to Buy and Sell Stock II

📌 Solution

1. Greedy Approach

Idea

Check reachability backwards

• Traverse the array backwards to check reachability
• Keep a marker idx as the current goal position
• If the current index can reach idx, move the goal to this index.

In the end, if the goal reaches index 0, it means the start can reach the end → return True.

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) (single pass)
• Space Complexity: O(1) (only one variable for profit)

2. Dynamic Programming Approach

Idea

Track two states for each day

• hold: maximum profit while holding a stock
• cash: maximum profit while not holding a stock

Transitions:

• hold = max(hold, cash - price) (buy or keep holding)
• cash = max(cash, hold + price) (sell or keep cash)

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
           
        hold = -prices[0]
        cash = 0
        
        for p in prices[1:]:
            hold = max(hold, cash - p)
            cash = max(cash, hold + p)
        return cash

• Time Complexity: O(n)
• Space Complexity: O(1) (two variables: hold and cash)