Best Time to Buy and Sell Stock II | Leetcode 122 | Recursion to Tabulation

You are given an array prices where prices[i] is the price of a stock on day i. You may complete as many transactions as you like. You must sell the stock before you buy again. Return the maximum profit you can achieve.

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

Example

Input:  prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price 1), sell on day 3 (price 5), profit 4.
Buy on day 4 (price 3), sell on day 5 (price 6), profit 3. Total 7.

Key idea: whenever there is an ascending step from prices[i] to prices[i+1], it is profitable to capture it.

Recursion

Intuition and Approach

Model decisions as a state machine on day index and a flag buy:

• If buy == 1, you can either buy today or skip.
• If buy == 0, you can either sell today or skip.

Recurse to the next day and choose the better of the two options for each state. Base case at the end returns 0 profit.

Code Implementation

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

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

Code explanation

• At each day, decide to act or skip based on buy state.
• Buying subtracts price, selling adds price, skipping adds zero.
• Maximum profit of subproblems composes the global maximum.

Time and Space Complexity

• Precise: each state branches twice without caching, so exponential time in n. Recursion depth up to n, so space O(n).
• Simplified: exponential time, linear space.

Conclusion

Correct but impractical for larger inputs due to repeated subproblems.

Memoization

Intuition and Approach

Cache the results for each (index, buy) to avoid recomputation. There are n * 2 states, each solved once.

Code Implementation

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

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

Code explanation

• dp[index][buy] stores the best profit from day index in the given state.
• Lookups prune the exponential tree to linear number of states.

Time and Space Complexity

• Precise: states 2n, each with O(1) transitions, so O(n) time. DP table O(n). Recursion stack O(n).
• Simplified: O(n) time, O(n) space.

Conclusion

A fast top down solution that passes constraints comfortably.

Tabulation

Intuition and Approach

Bottom up DP over days from right to left. dp[index][buy] holds the best profit from day index with state buy. Initialize base row at index = n to 0.

Code Implementation

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

Code explanation

• Fill the table from the end to the start using the same transition as memoization.
• The answer is the profit at day 0 when you are allowed to buy.

Time and Space Complexity

• Precise: O(n * 2) time and O(n * 2) space for the table.
• Simplified: O(n) time, O(n) space.

Conclusion

Iterative and stack free. Mirrors the memoized recurrence.

Tabulation (Space Optimization)

Intuition and Approach

The value at index depends only on index + 1. Keep two 2-element arrays: ahead for day index + 1, curr for day index.

Code Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        ahead = [0, 0]
        # ahead[0]=0
        # ahead[1]=0

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

Code explanation

• ahead[0] and ahead[1] represent best profits for the next day in states sellable and buyable respectively.
• Build curr from ahead, then roll forward.

Time and Space Complexity

• Precise: single pass over days with constant state work gives O(n) time and O(1) extra space.
• Simplified: O(n) time, O(1) space.

Conclusion

The most memory efficient DP version. Recommended for production.

Final takeaway

• The problem reduces to choosing buy or sell actions at each day to maximize profit.
• Recursion describes the choice structure but is exponential.
• Memoization and tabulation bring it to linear time.
• Space optimization keeps linear time with constant extra memory.

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