#309

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock with Cooldown

Maximize stock profit with cooldown restrictions using state transition dynamic programming to track buy, sell, and cooldown states.

array dynamic programming

Problem Statement

You are given an array of stock prices where each value represents the price of the stock on a specific day. Your goal is to maximize profit by performing as many buy and sell transactions as you want, subject to the rule that after selling a stock, you must wait one day before buying again due to a cooldown period.

You may not engage in multiple transactions simultaneously, meaning you must sell a stock before you can buy it again. The problem asks you to find the maximum profit achievable given these constraints.

Examples

Example 1

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

Output: 3

transactions = [buy, sell, cooldown, buy, sell]

Example 2

Input: prices = [1]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

State Transition DP Approach

Use dynamic programming to track three states: holding a stock, not holding a stock and in cooldown. Each state transitions based on the actions taken on the current day. The maximum profit is derived by considering the profits from holding, selling, and cooldown states on each day.

Tracking Profit for Each State

Define three variables for each day: one for holding a stock, one for not holding a stock but not in cooldown, and one for being in cooldown. Update these states progressively based on the day's stock price and previous state transitions. The result will be the maximum profit at the end of the array.

Optimizing Space Complexity

Since only the previous day's state information is needed, optimize space complexity by storing only the necessary states from the prior day instead of keeping the entire DP table. This reduces space requirements significantly while maintaining the same time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the prices array, as we process each day's price once. The space complexity can be optimized to O(1) by storing only the previous day's states, rather than maintaining a full DP table.

What Interviewers Usually Probe

Candidate correctly identifies the need for dynamic programming.
Candidate uses a space-optimized solution.
Candidate understands state transition and cooldown mechanics.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the cooldown after selling the stock.
Incorrectly calculating profit by not tracking the maximum at each state transition.
Using O(n) space when O(1) space is possible.

Follow-up variants

Modifying the problem to include transaction limits.
Allowing only one transaction (single buy and sell).
Adding more complicated cooldown conditions, such as cooldown lengths longer than one day.

FAQ

What is the primary pattern for solving 'Best Time to Buy and Sell Stock with Cooldown'?

The primary pattern is state transition dynamic programming, where you track states of holding, not holding, and being in cooldown to maximize profit.

How do I handle the cooldown period in the solution?

The cooldown is handled by tracking a 'cooldown' state after selling a stock. This ensures that you cannot immediately buy again.

Can the problem be solved with a greedy approach?

A greedy approach would not work for this problem due to the cooldown restriction, which makes dynamic programming necessary for correct results.

What is the time complexity of this solution?

The time complexity is O(n), where n is the length of the prices array, as each day is processed once.

How does GhostInterview assist with 'Best Time to Buy and Sell Stock with Cooldown'?

GhostInterview provides detailed explanations and helps optimize your approach through practice, guiding you in refining your solution for interview readiness.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i, j)$, which represents the maximum profit that can be obtained starting from the $i$th day with state $j$. The values of $j$ are $0$ and $1$, respectively representing currently not holding a stock and holding a stock. The answer is $dfs(0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 2, 0))
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Solution 2: Dynamic Programming

We can also use dynamic programming to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 2, 0))
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 2, 0))
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Continue Practicing

#312 burst balloons #313 super ugly number #300 longest increasing subsequence