Best Time to Buy and Sell Stock IV | Leetcode 188 | Recursion to Tabulation Approach

You are given an integer k and an array prices where prices[i] is the price of a stock on day i. You may complete at most k transactions in total. One transaction means one buy followed by one sell. You cannot hold multiple stocks at the same time, so you must sell before buying again.

Return the maximum profit you can achieve under these rules.

Here’s the [Problem Link] to begin with.

Example

k = 2, prices = [3, 2, 6, 5, 0, 3]
Answer = 7
Explanation:
Buy at 2, sell at 6  -> profit 4
Buy at 0, sell at 3  -> profit 3
Total profit = 7

This problem generalizes “Best Time to Buy and Sell Stock III” from a fixed limit of 2 transactions to a variable limit k. The core challenge is to choose which buy and sell pairs to execute so that the total profit is maximized while not exceeding k completed transactions.

Key idea that works for all solutions

At any day you are in one of two modes:

1. You are allowed to buy (not holding a stock)
2. You are allowed to sell (holding a stock)

You also track how many transactions you still have left to complete. A transaction is counted when you sell. This naturally leads to a state defined by three values:

• index the current day
• buy equals 1 if you can buy now, 0 if you should sell next
• limit the number of remaining transactions you can still complete

From this state you either take the action (buy or sell) or skip the day, and choose the option that yields higher profit.

Below we present four versions with increasing efficiency. We explain the problem only once here, then for each solution we cover Intuition and Approach, Code Implementation, Code explanation, Time and Space Complexity, and a short Conclusion.

Recursion

Intuition and Approach

Explore all valid choices by recursion:

• If there are no days left, profit is 0.
• If limit is 0, you cannot complete any more transactions, profit is 0.
• If buy == 1, you have two options:
  • Buy today. Profit becomes -prices[index] + solve(index + 1, 0, limit).
  • Skip today and stay in buy mode. Profit becomes solve(index + 1, 1, limit).
• If buy == 0, you have two options:
  • Sell today. Profit becomes prices[index] + solve(index + 1, 1, limit - 1) because a full transaction completes at sell.
  • Skip today and stay in sell mode. Profit becomes solve(index + 1, 0, limit).

Take the maximum of the two options in each case.

Code Implementation

class Solution:
    def solve(self, index, buy, limit, prices):
        if index == len(prices):
            return 0
        if limit == 0:
            return 0
        if buy == 1:
            buy_p = -prices[index] + self.solve(index + 1, 0, limit, prices)
            not_buy = 0 + self.solve(index + 1, 1, limit, prices)
            profit = max(buy_p, not_buy)
        else:
            sell = prices[index] + self.solve(index + 1, 1, limit - 1, prices)
            not_sell = 0 + self.solve(index + 1, 0, limit, prices)
            profit = max(sell, not_sell)
        return profit

    def maxProfit(self, k: int, prices: List[int]) -> int:
        return self.solve(0, 1, k, prices)

Code explanation

• Base cases handle end of array and exhausted transaction limit.
• On a buy day you either buy or skip. Buying subtracts price because it is cash outflow.
• On a sell day you either sell or skip. Selling adds price because it is cash inflow and reduces the remaining limit by 1.
• The recursion returns the best achievable profit from the current state.

Time and Space Complexity

• Precise: Exponential time due to branching at almost every step and recomputation of states. Recursion depth up to n, so stack space is O(n).
• Simplified: Exponential time, linear space.

Conclusion

This version is easy to understand but not efficient enough for large inputs.

Memoization

Intuition and Approach

Add caching so each state (index, buy, limit) is computed once. There are at most n * 2 * (k + 1) states.

Code Implementation

class Solution:
    def solve(self, index, buy, limit, prices, dp):
        if index == len(prices):
            return 0
        if limit == 0:
            return 0
        if dp[index][buy][limit] != -1:
            return dp[index][buy][limit]
        if buy == 1:
            buy_p = -prices[index] + self.solve(index + 1, 0, limit, prices, dp)
            not_buy = 0 + self.solve(index + 1, 1, limit, prices, dp)
            profit = max(buy_p, not_buy)
        else:
            sell = prices[index] + self.solve(index + 1, 1, limit - 1, prices, dp)
            not_sell = 0 + self.solve(index + 1, 0, limit, prices, dp)
            profit = max(sell, not_sell)
        dp[index][buy][limit] = profit
        return dp[index][buy][limit]

    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[-1 for _ in range(k + 1)] for _ in range(2)] for _ in range(n)]
        return self.solve(0, 1, k, prices, dp)

Code explanation

• dp[index][buy][limit] stores the optimal profit from that exact state.
• Before computing a state, the code checks the cache and returns the stored value if available.
• The transitions are identical to the recursive version, but repeated work is eliminated.

Time and Space Complexity

• Precise: Number of states ≈ n * 2 * (k + 1) and each state takes O(1) work once cached. Time O(n * k). The DP array uses O(n * k) space and recursion stack is O(n).
• Simplified: O(n * k) time, O(n * k) space.

Conclusion

Memoization is typically fast enough for large inputs and keeps the top down structure.

Tabulation

Intuition and Approach

Convert the memoized recurrence to bottom up. We build a 3D table dp[index][buy][limit] from the end to the beginning.

• Base rows
  • For all buy and limit, dp[n][buy][limit] = 0 because there are no days left.
  • For all index and buy, dp[index][buy][0] = 0 because there are no transactions left.
• Transition
  • Buy state: dp[index][1][limit] = max(-prices[index] + dp[index + 1][0][limit], dp[index + 1][1][limit])
  • Sell state: dp[index][0][limit] = max(prices[index] + dp[index + 1][1][limit - 1], dp[index + 1][0][limit])

Answer is dp[0][1][k].

Code Implementation

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[-1 for _ in range(k + 1)] for _ in range(2)] for _ in range(n + 1)]
        # Base Conditions
        for buy in range(0, 2):
            for limit in range(0, k + 1):
                dp[n][buy][limit] = 0
        for index in range(0, n + 1):
            for buy in range(0, 2):
                dp[index][buy][0] = 0
        for index in range(n - 1, -1, -1):
            for buy in range(0, 2):
                for limit in range(1, k + 1):
                    if buy == 1:
                        buy_p = -prices[index] + dp[index + 1][0][limit]
                        not_buy = 0 + dp[index + 1][1][limit]
                        profit = max(buy_p, not_buy)
                    else:
                        sell = prices[index] + dp[index + 1][1][limit - 1]
                        not_sell = 0 + dp[index + 1][0][limit]
                        profit = max(sell, not_sell)
                    dp[index][buy][limit] = profit
        return dp[0][1][k]

Code explanation

• The initialization ensures that impossible future actions yield zero profit.
• The inner loops fill the table for all combinations of index, buy, and limit, starting from the last day and moving backward.
• The recurrence mirrors exactly the choices from the recursive version.

Time and Space Complexity

• Precise: We fill n * 2 * (k + 1) states in constant time each, so time is O(n * k). The table takes O(n * k) space.
• Simplified: O(n * k) time, O(n * k) space.

Conclusion

Tabulation is iterative and avoids recursion depth limits while keeping performance optimal.

Tabulation (Space Optimized)

Intuition and Approach

dp[index][*][*] depends only on dp[index + 1][*][*]. Therefore, we can store only two slices:

• ahead represents the next day’s 2 by (k + 1) values
• curr represents the current day’s 2 by (k + 1) values

For each day, compute curr from ahead, then roll forward with ahead = curr.

Code Implementation

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        ahead = [[-1 for _ in range(k + 1)] for _ in range(2)]

        # Base: after the last day, profit is 0 for all states
        for buy in range(0, 2):
            for limit in range(0, k + 1):
                ahead[buy][limit] = 0
        # limit 0 is always 0 profit
        for buy in range(0, 2):
            ahead[buy][0] = 0

        for index in range(n - 1, -1, -1):
            curr = [[-1 for _ in range(k + 1)] for _ in range(2)]
            for buy in range(0, 2):
                for limit in range(0, k + 1):
                    if limit == 0:
                        profit = 0
                    elif buy == 1:
                        buy_p = -prices[index] + ahead[0][limit]
                        not_buy = 0 + ahead[1][limit]
                        profit = max(buy_p, not_buy)
                    else:
                        sell = prices[index] + ahead[1][limit - 1]
                        not_sell = 0 + ahead[0][limit]
                        profit = max(sell, not_sell)
                    curr[buy][limit] = profit
            ahead = curr
        return ahead[1][k]

Code explanation

• ahead is initialized to zeros because after the final day no further profit is possible.
• For each day we compute both buy and sell states for all limits from 0 to k.
• The final answer is at day 0 in buy mode with k transactions available, which is ahead[1][k].

Time and Space Complexity

• Precise: We still compute n * 2 * (k + 1) states, so time is O(n * k). We keep only two 2 by (k + 1) arrays, so extra space is O(k).
• Simplified: O(n * k) time, O(k) space.

Conclusion

This is the most memory friendly DP while maintaining optimal runtime. It is the recommended approach for production use.

Common pitfalls and tips

1. Decrement the transaction count on the sell action, not on buy. A transaction is counted when it completes.
2. Do not allow overlapping transactions. The buy state enforces the rule that you must sell before you buy again.
3. Initialize base cases carefully. When limit == 0 or index == n, the profit from that state is zero.
4. Edge cases
   • If k == 0 the answer is 0.
   • If prices is empty the answer is 0.
   • If k is very large (greater than n/2), the problem reduces to unlimited transactions. The provided DP still works, but a linear greedy solution for Stock II would also be valid.

Time and Space Complexity summary

• Recursion: exponential time, O(n) space for recursion depth
• Memoization: O(n * k) time, O(n * k) space
• Tabulation: O(n * k) time, O(n * k) space
• Space optimized tabulation: O(n * k) time, O(k) space

Conclusion

“Best Time to Buy and Sell Stock IV” is best solved by tracking three things at once: the day, whether you are in buy or sell mode, and how many transactions remain. Starting with a clear recursive model helps you see the decisions. Adding memoization or writing a bottom up DP turns it into a fast O(n * k) solution. Finally, compressing the DP across days brings memory down to O(k) while preserving correctness and performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.