LeetCode 123: Best Time to Buy and Sell Stock III Solution in Python – A Step-by-Step Guide

What Is LeetCode 123: Best Time to Buy and Sell Stock III?

In LeetCode 123: Best Time to Buy and Sell Stock III, you’re given an array prices where prices[i] is the stock price on day i. Your task is to find the maximum profit you can achieve with at most two buy-and-sell transactions, ensuring you sell before buying again (no overlapping trades). For example, with prices = [3, 3, 5, 0, 0, 3, 1, 4], the maximum profit is 6 (buy at 0, sell at 3 for 3; buy at 1, sell at 4 for 3).

Problem Statement

• Input: An integer array prices.
• Output: An integer—the maximum profit from up to two transactions.
• Rules:
• Buy before sell (sell day > buy day per transaction).
• At most two transactions, no overlapping (sell first before buying again).
• Return 0 if no profit possible.

Constraints

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁵

Examples

• Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
• Output: 6
• Why: Buy at 0, sell at 3 (3); buy at 1, sell at 4 (3); total = 6.
• Input: prices = [1, 2, 3, 4, 5]
• Output: 4
• Why: Buy at 1, sell at 5 (4); one transaction suffices.
• Input: prices = [7, 6, 4, 3, 1]
• Output: 0
• Why: Prices only decrease, no profit possible.

Understanding the Problem: Doubling the Trades

To solve LeetCode 123: Best Time to Buy and Sell Stock III in Python, we need to maximize profit with up to two transactions, finding the best buy-sell pairs without overlap. A brute force approach—trying all possible pairs of trades—would take O(n⁴) time, which is infeasible for 10⁵ elements. Instead, we’ll use optimization:

• Best Solution (DP with O(1) Space): O(n) time, O(1) space—tracks states dynamically.
• Alternative Solution (Two-Pass): O(n) time, O(n) space—splits into two profits.

Let’s dive into the Best Solution—dynamic programming—and break it down step-by-step.

Best Solution: Dynamic Programming with O(1) Space

Why This Is the Best Solution

The DP approach with O(1) space is the top pick because it’s both fast—O(n) time—and lean—O(1) space—while elegantly handling two transactions. It uses variables to track the cost and profit of each transaction at every step, updating them in one pass. It’s like managing a tiny portfolio, adjusting your holdings daily to maximize gains—efficient and ingenious!

How It Works

Here’s the strategy:

• Step 1: Define States:
• buy1: Cost of buying first stock (minimize).
• sell1: Profit after selling first stock (maximize).
• buy2: Cost of buying second stock after selling first (minimize).
• sell2: Profit after selling second stock (maximize).
• Step 2: Initialize:
• buy1 = buy2 = -infinity (no stock bought yet).
• sell1 = sell2 = 0 (no profit yet).
• Step 3: One Pass:
• For each price:
• Update buy1: Min of current cost or not buying.
• Update sell1: Max of current profit (sell at price) or not selling.
• Update buy2: Min of cost after first profit or not buying.
• Update sell2: Max of total profit or not selling.
• Step 4: Return:
• sell2 is the max profit with up to two trades.

Step-by-Step Example

Example: prices = [3, 3, 5, 0, 0, 3, 1, 4]

• Initialize: buy1 = -inf, sell1 = 0, buy2 = -inf, sell2 = 0.
• Day 0 (3):
• buy1 = max(-inf, -3) = -3.
• sell1 = max(0, 3-3) = 0.
• buy2 = max(-inf, 0-3) = -3.
• sell2 = max(0, 3-3) = 0.
• Day 1 (3):
• buy1 = -3.
• sell1 = 0.
• buy2 = -3.
• sell2 = 0.
• Day 2 (5):
• buy1 = -3.
• sell1 = max(0, 5-3) = 2.
• buy2 = max(-3, 2-5) = -3.
• sell2 = max(0, 5-3) = 2.
• Day 3 (0):
• buy1 = max(-3, -0) = 0.
• sell1 = max(2, 0-0) = 2.
• buy2 = max(-3, 2-0) = 2.
• sell2 = max(2, 0+2) = 2.
• Day 4 (0):
• buy1 = 0.
• sell1 = 2.
• buy2 = 2.
• sell2 = 2.
• Day 5 (3):
• buy1 = 0.
• sell1 = max(2, 3-0) = 3.
• buy2 = max(2, 3-3) = 2.
• sell2 = max(2, 3+2) = 5.
• Day 6 (1):
• buy1 = 0.
• sell1 = 3.
• buy2 = max(2, 3-1) = 2.
• sell2 = max(5, 1+2) = 5.
• Day 7 (4):
• buy1 = 0.
• sell1 = 3.
• buy2 = max(2, 3-4) = 2.
• sell2 = max(5, 4+2) = 6.
• Result: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Step 1: Initialize states
        buy1 = float('-inf')
        sell1 = 0
        buy2 = float('-inf')
        sell2 = 0

        # Step 2: One pass through prices
        for price in prices:
            # First transaction
            buy1 = max(buy1, -price)  # Min cost to buy
            sell1 = max(sell1, buy1 + price)  # Max profit after sell
            # Second transaction
            buy2 = max(buy2, sell1 - price)  # Min cost after first profit
            sell2 = max(sell2, buy2 + price)  # Max total profit

        return sell2

• Line 4-7: Initialize: negative infinity for buy costs, 0 for profits.
• Line 10-15: Loop through prices:
• Line 11: Update first buy cost.
• Line 12: Update first sell profit.
• Line 14: Update second buy cost using first profit.
• Line 15: Update total profit.
• Line 17: Return max profit with up to two trades.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—four variables.

This is a profit-juggling marvel!

Alternative Solution: Two-Pass Approach

Why an Alternative Approach?

The two-pass approach splits the problem into two parts—O(n) time, O(n) space—finding the max profit for one transaction up to each day, then combining with a second transaction. It’s like dividing the timeline into two trades and picking the best split—clear and insightful, though it uses more space.

How It Works

Here’s the plan:

• Step 1: First Pass (Left to Right):
• Compute max profit for one transaction up to each day.
• Step 2: Second Pass (Right to Left):
• Compute max profit for one transaction from each day to end.
• Step 3: Combine:
• Max of (first profit up to i + second profit after i).

Step-by-Step Example

Example: prices = [3, 3, 5, 0, 0, 3, 1, 4]

• First Pass (Left Profit):
• [0, 0, 2, 2, 2, 3, 3, 4].
• Second Pass (Right Profit):
• [4, 4, 4, 4, 4, 3, 3, 0].
• Combine:
• Day -1: 0 + 4 = 4.
• Day 0: 0 + 4 = 4.
• Day 1: 0 + 4 = 4.
• Day 2: 2 + 4 = 6.
• Day 3: 2 + 4 = 6.
• Day 4: 2 + 3 = 5.
• Day 5: 3 + 3 = 6.
• Day 6: 3 + 0 = 3.
• Result: 6.

Code for Two-Pass Approach

Copy codeclass Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        left_profit = [0] * n
        right_profit = [0] * n

        # First pass: Left to right
        min_price = prices[0]
        for i in range(1, n):
            min_price = min(min_price, prices[i])
            left_profit[i] = max(left_profit[i-1], prices[i] - min_price)

        # Second pass: Right to left
        max_price = prices[-1]
        for i in range(n-2, -1, -1):
            max_price = max(max_price, prices[i])
            right_profit[i] = max(right_profit[i+1], max_price - prices[i])

        # Combine
        max_profit = 0
        for i in range(n):
            max_profit = max(max_profit, left_profit[i] + right_profit[i])

        return max_profit

• Line 4-5: Arrays for profits.
• Line 8-11: Left pass for first trade.
• Line 14-17: Right pass for second trade.
• Line 20-22: Max of combined profits.
• Time Complexity: O(n)—two passes.
• Space Complexity: O(n)—two arrays.

It’s a split-profit calculator!

Comparing the Two Solutions

• DP O(1) Space (Best):
• Pros: O(n) time, O(1) space, single pass.
• Cons: Less intuitive states.
• Two-Pass (Alternative):
• Pros: O(n) time, O(n) space, clear split.
• Cons: More space, two passes.

DP wins for efficiency.

Additional Examples and Edge Cases

• [1, 2]: 1.
• [5, 4, 3]: 0.
• [1, 4, 2, 5]: 5.

Both handle these well.

Complexity Breakdown

• DP: Time O(n), Space O(1).
• Two-Pass: Time O(n), Space O(n).

DP’s leaner space shines.

Key Takeaways

• DP: Track two trades dynamically!
• Two-Pass: Split and combine!
• Profit: Balance two transactions.
• Python Tip: Variables optimize—see [Python Basics](/python/basics).

Final Thoughts: Double Your Gains

LeetCode 123: Best Time to Buy and Sell Stock III in Python is a trading challenge with flair. The DP approach maximizes with minimal space, while two-pass offers a clear divide. Want more stock fun? Try LeetCode 122: Best Time to Buy and Sell Stock II or LeetCode 188: Best Time to Buy and Sell Stock IV. Ready to trade? Head to Solve LeetCode 123 on LeetCode and cash in today!