309. Best Time to Buy And Sell Stock With Cooldown - Explanation

Problem Link

Description

You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.

You may buy and sell one NeetCoin multiple times with the following restrictions:

  • After you sell your NeetCoin, you cannot buy another one on the next day (i.e., there is a cooldown period of one day).
  • You may only own at most one NeetCoin at a time.

You may complete as many transactions as you like.

Return the maximum profit you can achieve.

Example 1:

Input: prices = [1,3,4,0,4]

Output: 6

Explanation: Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. Then buy on day 3 (price = 0) and sell on day 4 (price = 4), profit = 4-0 = 4. Total profit is 2 + 4 = 6.

Example 2:

Input: prices = [1]

Output: 0

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000


Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.


Hint 1

Try to think in terms of recursion and visualize it as a decision tree. Can you determine the possible decisions at each recursion step? Also, can you identify the base cases and the essential information that needs to be tracked during recursion?


Hint 2

At each recursion step, we can buy only if we haven't already bought a coin, or we can sell if we own one. When buying, we subtract the coin value, and when selling, we add it. We explore all possible buying and selling options recursively, iterating through the coins from left to right using index i. For the cooldown condition, if we buy a coin, we increment the index i by two.


Hint 3

We can use a boolean variable canBuy to indicate whether buying is allowed at the current recursive step. If we go out of bounds, we return 0. This approach is exponential. Can you think of a way to optimize it?


Hint 4

We can use memoization to cache the results of recursive calls and avoid recalculations. A hash map or a 2D array can be used to store these results.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

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

        def dfs(i, buying):
            if i >= len(prices):
                return 0

            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                return max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                return max(sell, cooldown)

        return dfs(0, True)

Time & Space Complexity

  • Time complexity: O(2n)O(2 ^ n)
  • Space complexity: O(n)O(n)

2. Dynamic Programming (Top-Down)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = {}  # key=(i, buying) val=max_profit

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            if (i, buying) in dp:
                return dp[(i, buying)]

            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]

        return dfs(0, True)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Dynamic Programming (Bottom-Up)

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

        for i in range(n - 1, -1, -1):
            for buying in [True, False]:
                if buying:
                    buy = dp[i + 1][False] - prices[i] if i + 1 < n else -prices[i]
                    cooldown = dp[i + 1][True] if i + 1 < n else 0
                    dp[i][1] = max(buy, cooldown)
                else:
                    sell = dp[i + 2][True] + prices[i] if i + 2 < n else prices[i]
                    cooldown = dp[i + 1][False] if i + 1 < n else 0
                    dp[i][0] = max(sell, cooldown)

        return dp[0][1]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Dynamic Programming (Space Optimized)

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

        for i in range(n - 1, -1, -1):
            dp_buy = max(dp1_sell - prices[i], dp1_buy)
            dp_sell = max(dp2_buy + prices[i], dp1_sell)
            dp2_buy = dp1_buy
            dp1_buy, dp1_sell = dp_buy, dp_sell

        return dp1_buy

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)