Space

Open

From Fieldwork

Scales

123. Best Time to Buy and Sell Stock III

leetcodearraydynamic-programminghard

v1

Since you can make at most two transactions and they cannot overlap, imagine splitting the array of prices into two parts at a specific day i.

The problem can be split into two sub-problems. If we are allowed two transactions, there must be some dividing line, say day i, where:

Transaction 1 happens on or before day i.
Transaction 2 happens on or after day i.

By iterating through every possible split point i and asking "What is the max profit on the left + max profit on the right?", you guarantee finding the global maximum.

To transition into the O(1) space solution, we can think:

Since Transaction 2 occurs after Transaction 1, we don't need to store the entire history of Transaction 1. We can just calculate the current state of T1 and feed it directly into the cost basis of T2 in the same loop. This removes the need for the array.

https://gemini.google.com/app/b5d7100d95f3bfaa

https://aistudio.google.com/prompts/1Lzk91exDfjXevJyCuhachpqQvj3eabzy

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        # 1. Forward Pass (Pre-compute Max Profit for Transaction 1)
        # left_profits[i] = max profit achievable from day 0 to i
        left_profits = [0] * n
        min_price = prices[0]
        
        for i in range(1, n):
            # Capture the lowest buy price seen so far
            min_price = min(min_price, prices[i])
            # Profit is either what we had before, or selling today
            left_profits[i] = max(left_profits[i-1], prices[i] - min_price)
            
        # 2. Backward Pass (Calculate Transaction 2 & Combine)
        # We don't need an array for right_profits; just a running max.
        max_price = prices[-1]
        right_profit = 0
        max_total_profit = 0
        
        # Iterate backwards to find the best second transaction
        for i in range(n - 1, -1, -1):
            # Capture the highest sell price seen from the right
            max_price = max(max_price, prices[i])
            
            # Profit for T2 if we bought on day i and sold at max_price
            current_right_profit = max_price - prices[i]
            
            # Keep track of the best T2 profit found from i to the end
            right_profit = max(right_profit, current_right_profit)
            
            # COMBINE:
            # T1 profit ending by day i (left_profits[i])
            # + T2 profit starting from day i (right_profit)
            current_total = left_profits[i] + right_profit
            max_total_profit = max(max_total_profit, current_total)
            
        return max_total_profit

v2

We can optimize the space by realizing this is essentially a reduction operation. We can just maintain the 'accumulated' best state for the two transactions as we iterate, without saving the history. We don't need the whole history of prices; we just need to carry the state of our wallet — specifically our costs and profits — forward one day at a time.

We can model the process as a sequence of 4 specific actions (states) that must happen in order:

Buy 1: Minimize the cost of the first stock.
Sell 1: Maximize the profit of the first transaction (Price - Buy 1).

Buy 2: Minimize the effective cost of the second stock. The "effective cost" is the current price minus the profit gained from the first transaction.
Sell 2: Maximize the total profit (Price - Effective Buy 2).

This order allows a single price spike to ripple through all transactions on the same day (Buy 1, Sell 1, Buy 2, Sell 2 all at once), which is mathematically valid (resulting in 0 extra profit) and ensures we never miss a peak.

We iterate through the prices once, updating these four variables.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Initialize costs to infinity and profits to 0
        buy1 = float('inf') # Cost of first stock
        profit1 = 0 # Profit after selling first stock

        buy2 = float('inf') # Cost of second stock (reinvested)
        profit2 = 0 # Profit after selling second stock

        for price in prices:
            # 1) Minimize the cost of the first stock
            buy1 = min(buy1, price)

            # 2) Maximize profit of the first transaction
            profit1 = max(profit1, price - buy1)

            # 3) Minimize cost of second stock
            # (Treat previous profit as a discount on the second buy price)
            buy2 = min(buy2, price - profit1)

            # 4) Maximize total profit after second transaction
            profit2 = max(profit2, price - buy2)
        return profit2

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeDec 28, 2025