LeetCode 188: Best Time to Buy and Sell Stock IV Solution in Python Explained

Problem Statement

In LeetCode 188, you’re given:

• prices: an integer array where prices[i] is the stock price on day i.
• k: an integer representing the maximum number of transactions (buy-sell pairs) allowed.

Your task is to return the maximum profit achievable by buying and selling the stock at most k times, where:

• You can only hold one stock at a time.
• You must sell before buying again.
• No shorting or fractional shares.

The result is an integer profit. This extends stock trading problems like LeetCode 121: Best Time to Buy and Sell Stock, adding multiple transactions, and differs from DNA sequence detection like LeetCode 187: Repeated DNA Sequences.

Constraints

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Example

Let’s see some cases:

Copy codeInput: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy at 2, sell at 4 (profit=2), no second transaction (1 too low).

Copy codeInput: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy at 2, sell at 6 (4), buy at 0, sell at 3 (3), total profit = 7.

Copy codeInput: k = 1, prices = [1,2]
Output: 1
Explanation: Buy at 1, sell at 2 (profit=1).

These examples show we’re maximizing profit with limited trades.

Understanding the Problem

How do you solve LeetCode 188: Best Time to Buy and Sell Stock IV in Python? Take k = 2, prices = [3,2,6,5,0,3]. We need the max profit with ≤ 2 buy-sell transactions. Possible trades:

• Buy at 2, sell at 6 (4 profit).
• Buy at 0, sell at 3 (3 profit).
• Total = 7.

Brute-forcing all transaction combinations is exponential, so we need dynamic programming (DP) to track profits across days and transactions efficiently. This isn’t a string task like LeetCode 186: Reverse Words in a String II; it’s about optimizing trades. We’ll use: 1. Dynamic Programming with State Tracking: O(nk) time, O(nk) space—our best solution. 2. Recursive with Memoization: O(nk) time, O(nk) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming with State Tracking Approach

Explanation

Dynamic Programming with State Tracking uses a 2D DP array to maximize profit:

• dp[i][t]: Max profit by day i with ≤ t transactions remaining (0-based indexing).
• States: t from 0 to k, i from 0 to n-1.
• For each day i and transaction t:
• Do nothing: dp[i][t] = dp[i-1][t].
• Sell today: Buy at min price before i, profit = prices[i] - min_price + dp[j-1][t-1] (j < i).
• Optimize by tracking min price dynamically.

This achieves O(nk) time (fill DP table), O(nk) space (DP array), and efficiency by avoiding recursion.

For k=2, [3,2,6,5,0,3]:

• Build DP table, max profit = 7 (two trades).

Step-by-Step Example

Example: k = 2, prices = [3,2,6,5,0,3]

Goal: Return 7.

• Step 1: Initialize DP array.
• n = 6, dp = [[0]*(k+1) for _ in range(n)] (6x3).
• Step 2: Fill DP table.
• i=0 (price=3): dp[0][0] = 0, dp[0][1] = 0, dp[0][2] = 0 (no sell yet).
• i=1 (price=2):
• t=0: 0 (no transactions).
• t=1: max(0, 2-3) = 0 (no profit).
• t=2: 0 (no sell yet).
• i=2 (price=6):
• t=0: 0.
• t=1: max(0, 6-2) = 4 (buy at 2, sell at 6).
• t=2: 4 (one trade so far).
• i=3 (price=5):
• t=0: 0.
• t=1: max(0, 5-2) = 3.
• t=2: 4 (no better second trade yet).
• i=4 (price=0):
• t=0: 0.
• t=1: max(0, 0-2) = 0.
• t=2: 4 (hold profit).
• i=5 (price=3):
• t=0: 0.
• t=1: max(0, 3-0) = 3.
• t=2: max(4, 3-0+dp[3][1]) = max(4, 3+3) = 6 (two trades).
• Step 3: Optimize with min price tracking (in code).
• Finish: dp[5][2] = 7 (buy 2, sell 6; buy 0, sell 3).

How the Code Works (Dynamic Programming with State Tracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef maxProfit(k: int, prices: list[int]) -> int:
    # Line 1: Handle edge cases
    if not prices or k == 0:
        # No prices or transactions (e.g., [], k=0)
        return 0

    # Line 2: Initialize variables
    n = len(prices)
    # Number of days (e.g., 6)
    dp = [[0] * (k + 1) for _ in range(n)]
    # DP array (e.g., 6x3 for k=2)

    # Line 3: Fill DP for each transaction
    for t in range(1, k + 1):
        # Transactions 1 to k (e.g., 1, 2)
        min_price = prices[0]
        # Track min price seen (e.g., 3)

        # Line 4: Fill DP for each day
        for i in range(1, n):
            # Days 1 to n-1 (e.g., 1 to 5)
            dp[i][t] = dp[i-1][t]
            # Do nothing (e.g., dp[0][1] = 0)

            # Line 5: Update min price
            min_price = min(min_price, prices[i] - dp[i-1][t-1])
            # Min buy price adjusted (e.g., 3, then 2)

            # Line 6: Sell today if profitable
            dp[i][t] = max(dp[i][t], prices[i] - min_price)
            # Max profit (e.g., 6-2=4 at i=2, t=1)

    # Line 7: Return max profit
    return dp[n-1][k]
    # e.g., dp[5][2] = 7

This detailed breakdown clarifies how DP with state tracking efficiently maximizes profit.

Alternative: Recursive with Memoization Approach

Explanation

Recursive with Memoization uses recursion with a memo table:

• Define dp(i, t): Max profit from day i with t transactions left.
• Base case: i ≥ n or t = 0 → 0.
• Recurse: Max of do nothing or buy/sell at each step.
• Memoize to avoid recomputation.

It’s a practical alternative, O(nk) time (memoized calls), O(nk) space (memo table), but involves recursion overhead.

For k=2, [3,2,6,5,0,3]:

• Recurse from i=0, t=2, memoize, max profit = 7.

Step-by-Step Example (Alternative)

For the same example:

• dp(0,2): Max(0, buy at 3 → dp(1,1)) → 7.
• dp(1,1): Max(0, buy at 2, sell at 6 → 4 + dp(3,0)) → 4.
• Finish: 7 (computed via memo).

How the Code Works (Recursive)

Copy codedef maxProfitRecursive(k: int, prices: list[int]) -> int:
    if not prices or k == 0:
        return 0
    n = len(prices)
    memo = {{

    def dp(i: int, t: int) -> int:
        if i >= n or t == 0:
            return 0
        if (i, t) in memo:
            return memo[(i, t)]
        profit = dp(i+1, t)  # Do nothing
        for j in range(i+1, n):
            if prices[j] > prices[i]:
                profit = max(profit, prices[j] - prices[i] + dp(j+1, t-1))
        memo[(i, t)] = profit
        return profit

    return dp(0, k)

Complexity

• Dynamic Programming with State Tracking:
• Time: O(n*k) – fill DP table.
• Space: O(n*k) – DP array.
• Recursive with Memoization:
• Time: O(n*k) – memoized calls.
• Space: O(n*k) – memo table.

Efficiency Notes

Dynamic Programming with State Tracking is the best solution with O(nk) time and O(nk) space, offering efficiency and clarity without recursion overhead—Recursive with Memoization matches complexity but uses recursion, making it slightly less efficient due to call stack, though equally effective.

Key Insights

• DP: Tracks transactions.
• Memo: Avoids recomputation.
• Transactions: Buy-sell pairs.

Additional Example

For k=1, prices=[1,2,3]:

• Goal: 2.
• DP: Buy 1, sell 3 → 2.

Edge Cases

• Empty Prices: 0.
• k=0: 0.
• Single Price: 0.

Both solutions handle these well.

Final Thoughts

LeetCode 188: Best Time to Buy and Sell Stock IV in Python is a complex trading challenge. The Dynamic Programming with State Tracking solution excels with its efficiency and clarity, while Recursive with Memoization offers a recursive approach. Want more? Try LeetCode 123: Best Time to Buy and Sell Stock III for k=2 or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 188 on LeetCode with k=2, [3,2,6,5,0,3], aiming for 7—test your skills now!