101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 5 main approaches to solve this problem:

  1. Brute Force Recursive Approach - Complex approach
  2. Memoized Recursive Approach - Complex approach
  3. Bottom-Up Dynamic Programming Approach - Complex approach
  4. Space-Optimized Dynamic Programming Approach - Complex approach
  5. State Machine Approach - Complex approach

Approach 1: Brute Force Recursive Approach

Let's start by understanding the problem from first principles. We need to find the maximum profit we can make by buying and selling stocks, with the constraint that after selling, we must wait one day before buying again.

Thinking Process: How would we approach this manually? Let's break down the problem:

  • We can buy and sell multiple times to maximize profit
  • After selling, we must wait one day (cooldown) before buying again
  • We can't buy and sell on the same day

At each day, we have different choices based on our current state:

  • If we don't have a stock: we can either buy a stock or do nothing
  • If we have a stock: we can either sell the stock or continue holding it
  • If we just sold a stock: we must wait one day (cooldown) before buying again

Intuition for Recursive Approach: We can model this as a decision tree where at each day we make the best choice. We need to keep track of whether we're holding a stock or not.

Let's define a recursive function dfs(i, holding) that returns the maximum profit starting from day i with the state holding (whether we are holding a stock or not).

Decision Logic:

  • If holding a stock: we can either sell it (and get the current price) or keep holding
  • If not holding: we can either buy a stock (and pay the current price) or do nothing
  • When we sell, we need to skip the next day (cooldown) before we can buy again

This recursive approach explores all possible buying and selling decisions and returns the maximum profit.

Algorithm:

  1. Define a recursive function dfs(i, holding) that returns the maximum profit starting from day i with the state holding.
  2. Base case: If i >= length of prices, return 0 (no more profit can be made).
  3. If holding is true (we have a stock):
  4. a. Option 1: Sell the stock and go to day i+2 (due to cooldown): prices[i] + dfs(i+2, false)
  5. b. Option 2: Continue holding the stock: dfs(i+1, true)
  6. c. Return the maximum of these two options.
  7. If holding is false (we don't have a stock):
  8. a. Option 1: Buy a stock: -prices[i] + dfs(i+1, true)
  9. b. Option 2: Do nothing: dfs(i+1, false)
  10. c. Return the maximum of these two options.
  11. Call dfs(0, false) to start the recursion from day 0 with no stock.

Time Complexity:

O(2^n)

Where n is the length of the prices array. In the worst case, we explore all possible combinations of buying and selling, which is exponential because at each step we have 2 choices and the recursion can go n levels deep.

Space Complexity:

O(n)

The space complexity is O(n) due to the recursion stack, which can go as deep as the number of days in the worst case.

Approach 2: Memoized Recursive Approach

The brute force approach works, but it's inefficient because we recalculate the same subproblems multiple times. Let's analyze why and how we can optimize it.

Problem with Brute Force: If we trace the recursion tree, we'll notice many overlapping subproblems. For example, the state (i=3, holding=true) might be calculated multiple times through different decision paths.

Thinking Process: How can we avoid recalculating the same states? We can use memoization (caching) to store the results of already computed states.

Key Insight: Our recursive function dfs(i, holding) depends only on two parameters:

  • The current day i
  • Whether we are holding a stock or not

There are only n * 2 possible states (n days, 2 holding states), so we can cache the results in a memo dictionary with keys (i, holding).

Optimization Strategy: Before computing a state, check if it's already in the memo. If yes, return the cached result. Otherwise, compute it, store it in the memo, and then return it.

Intuition: By storing the results of each state in a memo dictionary, we avoid redundant calculations and significantly improve the efficiency from exponential to linear time.

Algorithm:

  1. Create a memo dictionary to store the results of subproblems.
  2. Define a recursive function dfs(i, holding) that returns the maximum profit starting from day i with the state holding.
  3. If (i, holding) is in the memo, return the cached result.
  4. Base case: If i >= length of prices, return 0.
  5. If holding is true:
  6. a. Option 1: Sell the stock: prices[i] + dfs(i+2, false)
  7. b. Option 2: Continue holding: dfs(i+1, true)
  8. c. Store the maximum in memo[(i, holding)] and return it.
  9. If holding is false:
  10. a. Option 1: Buy a stock: -prices[i] + dfs(i+1, true)
  11. b. Option 2: Do nothing: dfs(i+1, false)
  12. c. Store the maximum in memo[(i, holding)] and return it.
  13. Call dfs(0, false) to start the recursion.

Time Complexity:

O(n)

Where n is the length of the prices array. With memoization, we solve each subproblem only once, and there are O(n * 2) = O(n) possible states (day × holding status).

Space Complexity:

O(n)

We use O(n) space for the memoization dictionary to store all possible states, plus O(n) for the recursion stack in the worst case, which simplifies to O(n).

Approach 3: Bottom-Up Dynamic Programming Approach

While the memoized approach is efficient, we can eliminate the recursion overhead by using a bottom-up dynamic programming approach.

Thinking Process: How can we convert our recursive solution to an iterative one? Let's analyze the dependencies in our recursive solution:

  • When we're at day i, we need information from days i+1 and i+2
  • This suggests we should fill our DP table from the end of the array to the beginning

DP State Definition: We can define a 2D DP array where:

  • dp[i][0]: Maximum profit starting from day i if not holding a stock
  • dp[i][1]: Maximum profit starting from day i if holding a stock

DP Transition: For each day i, we have:

  • If not holding: dp[i][0] = max(buy a stock, do nothing)
  • If holding: dp[i][1] = max(sell the stock, continue holding)

Handling Cooldown: When we sell a stock on day i, we need to look at the profit from day i+2 (skipping the cooldown day). This requires us to allocate extra space in our DP array to avoid out-of-bounds access.

Intuition: By working backwards from the end of the array, we ensure that all the necessary future states are already computed when we need them. This eliminates the need for recursion and gives us a clean iterative solution.

Algorithm:

  1. Create a 2D DP array dp of size (n+2) x 2, initialized with zeros. The extra 2 days are for handling cooldown safely.
  2. Iterate from i = n-1 down to 0:
  3. a. For not holding (j=0):
  4. - Option 1: Buy a stock: -prices[i] + dp[i+1][1]
  5. - Option 2: Do nothing: dp[i+1][0]
  6. - dp[i][0] = max of these two options
  7. b. For holding (j=1):
  8. - Option 1: Sell the stock: prices[i] + dp[i+2][0] (note the i+2 for cooldown)
  9. - Option 2: Continue holding: dp[i+1][1]
  10. - dp[i][1] = max of these two options
  11. Return dp[0][0] (maximum profit starting from day 0 with no stock).

Time Complexity:

O(n)

Where n is the length of the prices array. We process each day once, performing constant-time operations at each step.

Space Complexity:

O(n)

We use a 2D array of size (n+2) x 2, which is O(n) space. The extra space is needed to handle the cooldown period safely.

Approach 4: Space-Optimized Dynamic Programming Approach

The bottom-up DP approach works well, but we can further optimize the space usage.

Observation: If we look at our DP transitions carefully, we notice that for day i, we only need information from days i+1 and i+2. We don't need to store the entire DP array!

Thinking Process: How can we reduce the space complexity? Let's analyze what information we need to keep:

  • For day i, we need dp[i+1][0], dp[i+1][1], and dp[i+2][0]
  • This suggests we only need to keep track of values for the current day and the next two days

Space Optimization Strategy: Instead of using a full 2D array, we can use three arrays:

  • curr: For the current day
  • ahead: For the next day (i+1)
  • ahead2: For two days ahead (i+2)

Rolling Window Technique: As we move backwards through the days, we shift our window by updating:

  • ahead2 = ahead
  • ahead = curr

Intuition: By using this rolling window approach, we maintain only the necessary state information and reduce the space complexity from O(n) to O(1), while keeping the same time complexity.

Algorithm:

  1. Initialize variables for the next two days: ahead[0], ahead[1], ahead2[0], ahead2[1] (all set to 0).
  2. Iterate from i = n-1 down to 0:
  3. a. Create a new array curr[0], curr[1] for the current day.
  4. b. For not holding: curr[0] = max(-prices[i] + ahead[1], ahead[0])
  5. c. For holding: curr[1] = max(prices[i] + ahead2[0], ahead[1])
  6. d. Update ahead2 = ahead and ahead = curr for the next iteration.
  7. Return ahead[0] (maximum profit starting from day 0 with no stock).

Time Complexity:

O(n)

Where n is the length of the prices array. We process each day once, performing constant-time operations at each step, just like in the bottom-up approach.

Space Complexity:

O(1)

We only use a constant amount of extra space (three small arrays of size 2) regardless of the input size, which is a significant improvement over the O(n) space of the bottom-up approach.

Approach 5: State Machine Approach

Let's approach this problem from a different angle using a state machine model. This provides an intuitive way to understand the problem and leads to an elegant solution.

Thinking Process: What are the different states we can be in during the stock trading process? Let's identify them:

  • hold: We are currently holding a stock
  • sold: We have just sold a stock and are in cooldown
  • rest: We are not holding a stock and not in cooldown

State Transitions: How do we move between these states?

  • From hold: We can either continue holding or sell the stock
  • From sold: We can only go to rest (due to cooldown)
  • From rest: We can either continue resting or buy a stock

Profit Maximization: For each state, we want to maximize the profit:

  • hold = max(previous hold, previous rest - current price): Either continue holding or buy a new stock
  • sold = previous hold + current price: Sell the stock we were holding
  • rest = max(previous rest, previous sold): Either continue resting or come from sold state after cooldown

Visual Representation: We can visualize this as a state diagram where each state has transitions to other states, and each transition has an associated profit/cost.

Intuition: By tracking the maximum profit for each state as we go through the days, we can find the overall maximum profit at the end. Since we don't want to end up holding a stock, our final answer will be the maximum of the sold and rest states.

This state machine approach is elegant because it directly models the problem constraints and provides a clear mental model for understanding the solution.

Algorithm:

  1. Initialize hold = -prices[0] (maximum profit with a stock), sold = 0 (maximum profit after selling), and rest = 0 (maximum profit at rest).
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Save the current hold value in prevHold to avoid using the updated value in the same iteration.
  4. b. Calculate the new hold value: hold = max(hold, rest - prices[i]) (continue holding or buy).
  5. c. Calculate the new sold value: sold = prevHold + prices[i] (sell the stock).
  6. d. Calculate the new rest value: rest = max(rest, sold) (continue resting or come from sold).
  7. Return max(sold, rest) as the maximum profit (we don't want to end up holding a stock).

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use three variables (hold, sold, rest) regardless of the input size, making this approach very memory-efficient.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function maxProfit(prices):
    function dfs(i, holding):
        if i >= length of prices:
            return 0
 
        if holding:
            # Option 1: Sell the stock
            sell = prices[i] + dfs(i + 2, false)
            # Option 2: Continue holding
            hold = dfs(i + 1, true)
            return max(sell, hold)
        else:
            # Option 1: Buy a stock
            buy = -prices[i] + dfs(i + 1, true)
            # Option 2: Do nothing
            wait = dfs(i + 1, false)
            return max(buy, wait)
 
    return dfs(0, false)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone