Best Time to Buy and Sell Stock III | Leetcode 123 | Dynamic Programming Solution

You are given an array prices where prices[i] is the price of a stock on day i. You are allowed to complete at most two transactions in total. One transaction means one buy followed by one sell. You cannot hold more than one stock at a time, which means you must sell the stock before you buy again.

Your task is to return the maximum profit you can make under these rules.

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

Example

prices = [3,3,5,0,0,3,1,4]
Answer = 6
Explanation: 
Buy at 3, sell at 5 (profit 2), then buy at 1, sell at 4 (profit 3). 
An even better sequence is buy at 0, sell at 3 (profit 3) and buy at 1, sell at 4 (profit 3). Total 6.

The challenge is choosing the best two non-overlapping buy and sell pairs. This is harder than the unlimited transactions version because we must respect the limit of two transactions overall.

Intuition and approach (high level)

Think of each day as a decision point with a small set of choices. At any day you are in one of two moods:

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

In addition, you carry a third piece of information: how many transactions you can still complete. At the start you can complete 2 transactions. After you sell, this remaining limit is reduced by 1.

This leads to a natural dynamic programming state: (index, buy, limit) where

• index is the day,
• buy is 1 if you are allowed to buy, 0 if you should sell next,
• limit is how many transactions are still available.

At each state, try both options (take the action or skip) and keep the better profit.

Below are four versions that implement the same idea with increasing efficiency.

Recursion

Intuition and Approach

Use pure recursion to explore the decision tree.

• If limit == 0, you cannot make any further complete transactions, so profit from here is 0.
• If index == len(prices), you have no days left, so profit is 0.
• If buy == 1, you can either:
  • Buy today and pay prices[index], which makes you enter the sell state tomorrow with the same limit.
  • Skip buying today and stay in the buy state for the next day.
    Pick the better of these two.
• If buy == 0, you can either:
  • Sell today and gain prices[index], then move to buy state tomorrow with limit - 1 because one full transaction is completed.
  • Skip selling today and stay in the sell state for the next day.

This explores all valid sequences of up to two transactions.

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, prices: List[int]) -> int:
        n = len(prices)
        return self.solve(0, 1, 2, prices)

Code explanation

• Base cases stop the recursion when there are no days left or when there are no transactions left.
• At each day, compare the profit of acting now versus waiting for a future day.
• Subtracting price on buy and adding price on sell models cash flow correctly.
• The returned profit is the maximum over all explored paths.

Time and Space Complexity

• Precise: Without caching, the number of states grows exponentially because the recursion branches at almost every step. Time is exponential in n. The maximum recursion depth is O(n), so stack space is O(n).
• Simplified: Exponential time, linear space.

Conclusion

Plain recursion is clear to understand but too slow for large inputs because it recomputes many identical subproblems.

Memoization

Intuition and Approach

Add a 3D DP cache dp[index][buy][limit] to remember answers already computed. This reduces the number of subproblems to n * 2 * 3, and each is solved once.

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, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n)]
        return self.solve(0, 1, 2, prices, dp)

Code explanation

• The cache stores computed results for each combination of (index, buy, limit).
• Before any computation, check if the value exists in dp and reuse it.
• This avoids re-exploring the same future repeatedly.

Time and Space Complexity

• Precise: There are at most n * 2 * 3 states, each taking O(1) work to compute once cached, so time is O(n). The DP array uses O(n * 2 * 3) = O(n) space, and recursion stack uses O(n) space.
• Simplified: O(n) time, O(n) space.

Conclusion

Memoization keeps the clarity of recursion and is efficient enough for large inputs.

Tabulation

Intuition and Approach

Convert the top down recurrence into a bottom up DP table. We will build dp[index][buy][limit] from the end toward the start.

• 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 no transactions remain.
• Transition:
  • If buy == 1, choose max(-prices[index] + dp[index+1][0][limit], dp[index+1][1][limit]).
  • If buy == 0, choose max(prices[index] + dp[index+1][1][limit-1], dp[index+1][0][limit]).

Finally answer is dp[0][1][2].

Code Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)]
        # Base Conditions
        for buy in range(0, 2):
            for limit in range(0, 3):
                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, 3):
                    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][2]

Code explanation

• The triple nested loops fill the DP from the last day back to day 0.
• The base initializations ensure that when we try to look up impossible states like limit == 0, we get 0 profit.
• The transitions exactly mirror the recursive choices, but computed iteratively.

Time and Space Complexity

• Precise: We fill n * 2 * 3 states with constant time work each, so time is O(n). The table stores O(n * 2 * 3) values, so space is O(n).
• Simplified: O(n) time, O(n) space.

Conclusion

Tabulation is iterative and avoids recursion depth limits while keeping the same optimal result.

Tabulation (Space Optimization)

Intuition and Approach

Observe that dp[index][*][*] depends only on dp[index + 1][*][*]. Therefore, we can store only two 2×3 layers:

• ahead represents day index + 1.
• curr represents day index.

Update curr from ahead for all states and then roll ahead = curr.

Code Implementation

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

        for buy in range(0, 2):
            for limit in range(0, 3):
                ahead[buy][limit] = 0
        for buy in range(0, 2):
            ahead[buy][0] = 0
        for index in range(n - 1, -1, -1):
            curr = [[-1 for _ in range(3)] for _ in range(2)]
            for buy in range(0, 2):
                for limit in range(0, 3):
                    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][2]

Code explanation

• ahead is the DP layer for the next day and is initialized to 0 because after the last day profit is zero regardless of state.
• For each day moving backward, compute all 6 states in curr using ahead.
• The answer at the end is the state where you are at day 0, allowed to buy, with two transactions available, which is ahead[1][2].

Time and Space Complexity

• Precise: We still process n * 2 * 3 states, so time is O(n). We store two 2×3 matrices, so space is O(1).
• Simplified: O(n) time, O(1) extra space.

Conclusion

This version keeps the optimal time while using constant extra memory. It is the best practical approach for production because it is both fast and memory efficient.

Common pitfalls and tips

1. Forgetting to reduce limit only on a sell. The transaction completes when you sell, not when you buy.
2. Allowing overlapping transactions by buying again before selling. The state buy prevents that by forcing a sell before the next buy.
3. Off-by-one errors in base conditions. If limit == 0 or index == n, no profit is possible from that point onward.
4. Negative prices or empty arrays are not present in the problem, but make sure your base checks handle n == 0.

Time and Space Complexity summary

• Recursion: exponential time, O(n) space (stack).
• Memoization: O(n) time, O(n) space.
• Tabulation: O(n) time, O(n) space.
• Space-optimized tabulation: O(n) time, O(1) space.

Here O(n) hides the constant factor of 6 coming from 2 buy states × 3 limits per day.

Conclusion

The key to solving Best Time to Buy and Sell Stock III is to track three things at once: the current day, whether you are allowed to buy or should sell, and how many transactions remain. Starting from a simple recursive model, we add memoization to remove repeated work, then convert to an iterative DP, and finally compress the DP to constant space. All efficient versions run in linear time with respect to the number of days and respect the maximum of two transactions.

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