Best Time to Buy and Sell Stock with Cooldown

Solution Approach

Let us look into different approaches for solving this problem.

Recursion Approach

In this problem, before starting a new transaction, we’re first required to sell the last stock we bought. Now let’s assume that we buy a stock on day ‘i’. To sell this stock, we need to find a day ‘j’, such that j>i and j<n, where ‘n’ is the total number of the elements in the array. 

Now let’s assume that there are many such j’s. So the question is which one should we choose? Now see that if we decide on one such j, then for the subsequent transactions, we have reduced our search space from j+1 to n-1. 

Again, we need to do the same process for our new search space. Therefore, recursion can be used in this problem. 

The idea is that on any day, we have two options regarding buying the stock. Either we buy it on that day, or we don’t. We maintain a bool variable “CanBuy”, which tells us this. If we can buy stock on day ith, CanBuy will be 1; otherwise, it will be 0. 

Now, if we can buy on day ith, we further have two options:

• Simply buy the stock on day ith so the profit will be reduced by the cost of the stock at that index and then look for the profit from day ith +1 with CanBuy = 0.
   
• Or, don’t buy the stock on day ith, rather, move to day ith +1 with CanBuy=1. 
   

If we have to sell the stock on day ith, we further have two options:

• Sell the stock on day ith and add the cost of the stock at this day to the profit. Now, since we’ve sold the stock on day i, i+1 will be a cooldown day and therefore, next what we can do is, move to day i+2 with canBuy = 1.
   
• Or, don’t sell the stock on day i, rather, move to day i+1 with CanBuy = 0.
   

We’ll make a function named “recur” which will do the above calculations for the ith day.

Algorithm 

1. Input the number of days, say ‘n’, and the prices on all ‘n’ days.
    
2. Call the Maximum_Profit function with the parameter prices, which will basically return the final answer. 
    
3. In the Maximum_Profit function, since on the first day we can only buy the stock, call the “recur” function with CanBuy == true for day 0. 
    
4. In the “recur” function, check if we’ve reached the end of the process vector. If yes, return 0 as no further profit can be made.
    
5. Otherwise, if CanBuy is true, which means we can buy stock on day i, calculate the profit for the two subproblems and return the maximum of these two. The subproblems are -
     
   
   1. Simply buy the stock on day i so the profit will be reduced by the cost of the stock at that index and then call “recur” for index i+1 with canBuy = 0, i.e., call recur(prices, i+1,0) and subtract prices[i] from it.
       
   2. Or, don’t buy the stock on day i, rather, move to day i+1 with canBuy=1 i.e., call recur(prices, i+1,1).
       
   3. Return max of the above two.
       
6. If the CanBuy is false, again explore the two options for the false condition discussed above and return the maximum of those two. The subproblems are -
    
   1. Sell the stock on day i and add the cost of the stock on this day to the profit. Call recursion for i+2 with canBuy=1, as i+1th day will be the cooldown day, i.e., call recur(prices,i+2,1) and add prices[i] to it. 
       
   2. Or, don’t sell the stock on day i, rather, move to day i+1 with canBuy = 0 i.e., call recur(prices,i+1,0).
       
   3. Return max of the above two.
       
7. Maximum_Profit will return the answer to the main function. So just print it. 

Dry Run

The array of the prices is given as prices = [2, 3, 3, 0, 2]. Initially the can_buy = 1. Let's see the function call for index = 0. ‘a’ stores the value of the recursive call made when either a buy or sell operation is being performed and ‘b’ stores the value, when the current index is skipped i.e. neither buy nor sell the operation, is being performed on that index.

At index = 0, we have two choices: buy or skip. If we perform a buy operation, the profit will be -2 + recur ( index+1 ). The CanBuy will become 0, as we are now holding stock. If we skip the operations, the profit will recur ( index+1 ).

The above operations will call for index = 1. Now when CanBuy = 0. We can either sell the stock or skip it. If we perform the sell operation, profit will be 3 + recur ( index+1 ), and CanBuy will be set to 1.

Next time when the operation is called for index = 2 and the sell operation is performed at index=1 then this index skip will serve as a cooldown period.

This way, the function calls will work until the base condition is reached and we will receive a final output of 3 as our maximum profit.

Let's now see the C++ implementation for the same.

Implementation in C++

Below is the C++ implementation of the above-discussed approach.

#include <bits/stdc++.h>
using namespace std;

// Function to call the recursion
int recur(vector<int>& prices,int idx,bool CanBuy){
    /*
        If we reach the end of the vector, 
        return 0 as no further profit can be made.
    */
    if(idx>=prices.size())
        return 0;
    int x,y;

    if(CanBuy==1){ 
        // If we can buy, we have these two options. Return the maximum of these two
        x=recur(prices,idx+1,0)-prices[idx];  
        y=recur(prices,idx+1,1);
        return max(x,y);
    }
    else{
        // If we can sell, we have these two options. Return the maximum of these two.
        x=prices[idx]+recur(prices,idx+2,1);
        y=recur(prices,idx+1,0);
        return max(x,y);
    }
}

int Maximum_Profit(vector<int>& prices) {

    // Taking initial index 0
    int idx=0;
    
    /*
    	Calling the recursion function and 
    	Starting with index 0 call recur with CanBuy = 1. 
    */
    return recur(prices,idx,1); 
}

int main(){

    // Number of days
    int n=5; 

    // Declaration of prices 
    vector <int> prices(n);
    prices[0]=2;
    prices[1]=3;
    prices[2]=3;
    prices[3]=0;
    prices[4]=2;
    
    // Calling the Maximum_Profit function
    int profit = Maximum_Profit(prices); 
    cout<<profit<<endl;
    return 0;
}

Output

Implementation in Java

import java.util.*;

public class MyClass {
    // Function to calculate the profit using recursion
    static int n;
    static int recur(int prices[],int idx,boolean CanBuy){
        
        // If we reach the end of the array, return 0.
        if(idx>=n)
        return 0;
        
        int x,y;
        if(CanBuy==true){
         
            // If we can buy, we have these two options. Return the maximum of these two.
            x=recur(prices,idx+1,false)-prices[idx];  
            y=recur(prices,idx+1,true);
            return Math.max(x,y);
        }
        else{
        
            // If we can sell, we have these two options. Return the maximum of these two.
            x=prices[idx]+recur(prices,idx+2,true);
            y=recur(prices,idx+1,false);
            return Math.max(x,y);
        }
    }
    
    // Function to calculate the Maximum Profit.
    static int Maximum_Profit(int prices[]){
    
        // Taking initial index 0
        int idx=0;
        
        /*
        	Calling the recursion function and 
        	Starting with index 0 call recur with CanBuy = 1.
        */ 
        return recur(prices,idx,true); 
    }
    
    // Driver Function
    public static void main(String args[]) {
    
        // Number of days
        n=5; 
        
        // Declaration of prices vector
        int prices[];
        prices=new int[n];
        prices[0]=2;
        prices[1]=3;
        prices[2]=3;
        prices[3]=0;
        prices[4]=2;
        
        // Calling the Maximum_Profit function
        int profit = Maximum_Profit(prices); 
        System.out.println(profit);
    }
}

Output

Time Complexity

O(2^N), where ‘N’ is the number of days.

Explanation: In the worst case, for every index, we make two recursive calls as we have two options. The maximum depth of the recursion tree can go up to ‘N’. Hence the time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the number of days.

Explanation: In the worst case, the extra space used by the recursion stack can go up to a  maximum depth of ‘N’. Hence the space complexity is O(N).

Dynamic Programming Approach

The time complexity of the above approach is exponential and thus is not optimal from the interview point of view. In the above recursive approach, we have overlapping subproblems and optimal substructure. Therefore, we can optimize it using dynamic programming.

What we do is memorize the results of each pair of index i and canBuy state in a dp lookup table. The dp table will be a 2-D table with size [n]x[2] as there can be n indexes and the canBuy variable has a maximum of two different types of values (0 or 1). 

If we call the function “recur” with some state (i, CanBuy) that has already been calculated, we just simply return the memorized solution. This will help reduce the time complexity as we don’t do repeated calculations at any time. 

For this, initially, in the dp table, we initialize the values with -1 and we keep updating the answer for the current (i, CanBuy) state. If there is a state whose dp value is not equal to -1, this means that we’ve already calculated the value for this state. So we just return the memorized dp value. 

The rest of the whole idea is the same.

Algorithm

1. Input the number of days, say ‘n’, and the prices on all ‘n’ days.
    
2. Call the Maximum_Profit function with the parameter prices, which will basically return the final answer. 
    
3. In the Maximum_Profit function, since on the first day we can only buy the stock, call the “recur” function with canBuy ==true for day 0. 
    
4. In the “recur” function, check if we’ve reached the end of the process vector. If yes, return 0 as no further profit can be made.
    
5. Check if the current (i,canBuy) state already has an answer calculated, i.e., see if dp[i][canBuy] is != -1. If true, then the answer is already calculated, so just return it. Otherwise, continue with the following steps.
    
6. if canBuy is true, which means we can buy stock on day i, calculate the profit for the two subproblems and return the maximum of these two. The subproblems are -
    
   1. Simply buy the stock on day i so the profit will be reduced by the cost of the stock at that index and then call “recur” for index i+1 with CanBuy = 0, i.e., call recur(prices, i+1,0) and subtract prices[i] from it.
       
   2. Or, don’t buy the stock on day i, rather, move to day i+1 with CanBuy=1 i.e., call recur(prices, i+1,1).
       
   3. Return and store the max of the above two in dp[i][canBuy].
       
7. If the canBuy is false, again explore the two options for the false condition discussed above and return the maximum of those two. The subproblems are -
    
   1. Sell the stock on day i and add the cost of the stock on this day to the profit. Call recur for i+2 with canBuy=1, as i+1th day will be the cooldown day, i.e., call recur(prices,i+2,1) and add prices[i] to it. 
       
   2. Or, don’t sell the stock on day i, rather, move to day i+1 with CanBuy = 0 i.e., call recur(prices,i+1,0).
       
   3. Return and store the max of the above two in dp[i][CanBuy].
       
8. Maximum_Profit will return the answer to the main function. So just print it. 
    

Implementation in C++

Below is the C++ implementation of the above-discussed dp approach.

#include <bits/stdc++.h>
using namespace std;

// 2-D dp array for storing the results
int dp[501][2];

// Recursive function for calculating maximum profit
int recur(vector<int>& prices,int idx, bool CanBuy){
    
    // If we reach the end of the vector, return 0 as no further profit can be made.
    if(idx>=prices.size())  
        return 0;
    if(dp[idx][CanBuy]!=-1){ 
        
        // Value for this state is already calculated, so just return it.
        return dp[idx][CanBuy] ;
    }
    
    int x,y;
    if(CanBuy==1){ 
        
        // If we can buy, we have these two options. Return the maximum of these two
        x=recur(prices,idx+1,0)-prices[idx];  
        y=recur(prices,idx+1,1);
        return dp[idx][CanBuy] = max(x,y);
    }
    else{
        
        // if we can sell, we have these two options. Return the maximum of these two.
        x=prices[idx]+recur(prices,idx+2,1);
        y=recur(prices,idx+1,0);
        return dp[idx][CanBuy] = max(x,y);
    }
}

int Maximum_Profit(vector<int>& prices) {
    
    // Taking initial index 0
    int idx=0;
    memset(dp,-1,sizeof(dp));
    
    // Calling the recursion function and Starting with index 0 call recur with CanBuy = 1. 
    return recur(prices,idx,1); 
}

int main(){
    
    // Number of days
    int n=5; 

    // Declaration of prices vector
    vector <int> prices(n);  
    prices[0]=2;
    prices[1]=3;
    prices[2]=3;
    prices[3]=0;
    prices[4]=2;
    
    // Calling the Maximum_Profit function
    int profit = Maximum_Profit(prices); 
    cout<<profit<<endl;
    return 0;
}

Output

Implementation in Java

import java.util.*;

public class MyClass {
    
    // Function to calculate the profit using recursion
    static int n;
    static int dp[][] = new int[501][2];
    static int recur(int prices[],int idx,int CanBuy){
        
        // If we reach the end of the array, return 0.
        if(idx>=n)
        return 0;
        
        if(dp[idx][CanBuy]!=-1){ 
            
            // Value for this state is already calculated, so just return it.
            return dp[idx][CanBuy] ;
        }
        
        int x,y;
        if(CanBuy==1){ 
            /* 
                If we can buy, we have these two options. 
                Return the maximum of these two
            */
            x=recur(prices,idx+1,0)-prices[idx];  
            y=recur(prices,idx+1,1);
            return dp[idx][CanBuy] = Math.max(x,y);
        }
        else{
            /*
                If we can sell, we have these two options. 
                Return the maximum of these two.
            */
            x=prices[idx]+recur(prices,idx+2,1);
            y=recur(prices,idx+1,0);
            return dp[idx][CanBuy] = Math.max(x,y);
        }
    }
    
    // Function to calculate the Maximum Profit.
    static int Maximum_Profit(int prices[]){
        
        // Taking initial index 0
        int idx=0;
        
        for(int i=0;i<=500;i++){
            
            dp[i][0]=-1;
            dp[i][1]=-1;
        }
        /* 
            Calling the recursion function and 
            Starting with index 0 call recur with CanBuy = 1. 
        */
        return recur(prices,idx,1); 
    }
    
    // Driver Function
    public static void main(String args[]) {
        
        // Number of days
        n = 5;
        
        // Declaration of prices vector
        int prices[];
        prices=new int[n]; 
        prices[0]=2;
        prices[1]=3;
        prices[2]=3;
        prices[3]=0;
        prices[4]=2;
        
        // Calling the Maximum_Profit function
        int profit = Maximum_Profit(prices); 
        System.out.println(profit);
    }
}

Output

Time Complexity

O(N), where ‘N’ is the total number of days.

Explanation: For every i, we’re calculating the value of dp[i][CanBuy] only once. We are calling the function ‘recur’ a repeated number of times but we are doing the calculation only once.

Hence, the advantage of storing the results in the dp array;

Space Complexity

O(2*N), where ‘N’ is the number of days.

Explanation: The extra is the space used by the dp table. Since the size of the dp table is 2*N, the space complexity is O(2*N) which is equivalent to O(N).

Check out Longest Common Substring

Constant Space Solution

The space complexity of the previous solution was O(N). So, if we can optimize it to a constant Space Solution i.e. O(1), we should surely go ahead and implement it. Let’s see how we can do that.

Let’s define two arrays buy and sell: 

1. buy[i]: the maximum profit up to the day i with buy as the last action.
2. sell[i]: the maximum profit up to the day i with sell as the last action.
    

In that case, the recurrence relations will be:

1. buy[i] = max ( sell[i - 2] - price[i], buy[ i - 1 ])
     
   • Explanation: buy[i] will be the profit with buy as the last action. So on the day i, if we don’t do any of the activity, i.e., if we take rest, it means we must have done the “buy” action on some previous day. So buy[i-1] can give the information about that. In case we do the “buy” action on the day i, the profit will be ( sell[i - 2]-price[i] ) because the (i-1)th day will be the cooldown. 
      
2. sell[i] = max( buy[i - 1]+price[i], sell[ i - 1 ])
   
   
   • Explanation: sell[i] will be the profit with sell as the last action. So on the day i, if we don’t do any of the actions, i.e, if we take a rest, it means we must have done the “sell” action on some previous day. So sell[i-1] can give the information about that. In case we actually do the “sell” action on the day i, the profit will be (buy[i - 1]+price[i]) because we must have brought the stock on some day before i so that we’re able to sell it on the day i.
      

Thus we can see that with “buy” as the last action, the profit on the day i depends on the profit of day (i-1) and the selling profit of day (i-2). Similarly, with “sell” as the last action, the profit on day i depends on the profit of day (i-1) and buying profit of day (i-1). So, if we store these 5 values in some variables we can achieve a constant space complexity.

Algorithm 

1. We initialize 5 variables. 
   1. Buy which denotes buy[i] to 0
       
   2. Buy_Prev which denotes buy[i-1] to INT_MIN 
       
   3. Sell which denotes sell[i] to 0
       
   4. Sell_Prev1 which denotes sell[i-1] to 0
       
   5. Sell_Prev2 which denotes sell[i-2] to 0
       
2. Traverse the prices vector. For each price curr in the vector,
   1. Update Buy = max(Buy_Prev, Sell_Prev2 - curr)
       
   2. Update Sell = max(Sell_Prev1, Buy_Prev + curr)
       
   3. For the next iteration, Update the corresponding values 
      1. Buy_Prev=Buy
          
      2. Sell_Prev2 = Sell_Prev1
          
      3. Sell_Prev1 = Sell
          
3. Return the value of sell as the last action we must have done would be sold.

Dry Run

Input:

We will perform 5 steps in each iteration and they are as follows:

1. Buy = max(Buy_Prev, Sell_Prev2 - curr);
2. Sell = max(Sell_Prev1, Buy_Prev + curr);
3. Buy_Prev = Buy;
4. Sell_Prev2 = Sell_Prev1;
5. Sell_Prev1 = Sell;
    

Current index = 0

Next index = 1

Next index = 2

Next index = 3

Final index = 4

Our maximum profit till now with a cooldown period is stored in the variable ‘Sell’ which has a value of 3. Hence, the output will be 3 for this input.

Implementation in C++

Below is the C++ implementation of the above-discussed approach.

#include <bits/stdc++.h>
using namespace std;

// Function for calculating maximum profit
int Maximum_Profit(vector<int>& prices) {
      int Buy; /*buy[i]*/ 
      int Buy_Prev = INT_MIN; /*buy[i-1]*/
      int Sell = 0; /*sell[i]*/ 
      int Sell_Prev1 = 0; /*sell[i-1]*/ 
      int Sell_Prev2 = 0; /*sell[i-2]*/
      
      // Looping through all prices array
      for (auto curr: prices) {
        // Updating the value of buy for the current price 'curr'
        Buy = max(Buy_Prev, Sell_Prev2 - curr);
        
        // Updating the value of sell for the current price 'curr'
        Sell = max(Sell_Prev1, Buy_Prev + curr);
        
        // Update all the previous values for the next iteration
        Buy_Prev = Buy;
        Sell_Prev2 = Sell_Prev1;
        Sell_Prev1 = Sell;
      }
      
      return Sell;
}

int main(){
    
    // Number of days
    int n=5; 

    // Declaration of prices vector
    vector <int> prices(n);  
    prices[0]=2;
    prices[1]=3;
    prices[2]=3;
    prices[3]=0;
    prices[4]=2;
    
    // Calling the Maximum_Profit function
    int profit = Maximum_Profit(prices); 
    cout<<profit<<endl;
    return 0;
}

Output

Implementation in Java

import java.util.*;

public class MyClass {
    // Function to calculate the profit using recursion
    static int n;

    // Function for calculating maximum profit
    static int Maximum_Profit(int prices[]) {
          int Buy; /*buy[i]*/ 
          int Buy_Prev = -100000000; /*buy[i-1]*/
          int Sell = 0; /*sell[i]*/ 
          int Sell_Prev1 = 0; /*sell[i-1]*/ 
          int Sell_Prev2 = 0; /*sell[i-2]*/
          
          // Looping through all prices array
          for (int curr: prices) {
            // Updating the value of buy for the current price 'curr'
            Buy = Math.max(Buy_Prev, Sell_Prev2 - curr);
            
            // Updating the value of sell for the current price 'curr'
            Sell = Math.max(Sell_Prev1, Buy_Prev + curr);
            
            // Update all the previous values for the next iteration
            Buy_Prev = Buy;
            Sell_Prev2 = Sell_Prev1;
            Sell_Prev1 = Sell;
          }
          
          return Sell;
    }
    
    // Driver Function
    public static void main(String args[]) {
        
        // Number of days
        n=5;
        
        // Declaration of prices vector
        int prices[];
        prices=new int[n]; 
        prices[0]=2;
        prices[1]=3;
        prices[2]=3;
        prices[3]=0;
        prices[4]=2;
        
        // Calling the Maximum_Profit function
        int profit = Maximum_Profit(prices); 
        System.out.println(profit);
    }
}

Output

 

Time Complexity

O(N), where ‘N’ is the number of days.

Explanation: We’re just iterating through the whole prices vector once.

Space Complexity

O(1)

Explanation: The only spaces taken here are by the 5 variables that just take constant space. 

Check out this problem - Minimum Coin Change Problem 

Frequently Asked Questions

Write some applications of Dynamic Programming.

DP finds applications in optimization, combinatorial, graph algorithms, and string problems.

What is dynamic programming, and where is it used?

Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

What are overlapping subproblems?

 A problem has overlapping subproblems if it can be divided into smaller problems that are reused multiple times.

What is the optimal substructure?

If an optimal solution can be created from the optimal solutions of its subproblems, a problem is said to have an optimal substructure.

What is the difference between DP and Divide and Conquer?

In divide and conquer, we solve the subproblems independently, and they do not depend on each other. In dynamic programming, the solution to each subproblem depends on the answers to smaller subproblems, which are interdependent.

When does a stock transaction give profit?

When you sell the stock at a price that is higher than the price at which you bought it, the stock transaction gives a profit.

How do we calculate the time complexity of dynamic programming?

The time complexity of Dynamic programming is O(k*n), k is the number of states that need to be operated, and n is the time complexity of each operation on each form. 

Conclusion

This article discusses the best time to buy and sell the stock with the cooldown problem. In detail, we have covered three different approaches to solving the problem and we saw the implementation of all three approaches in C++ and Java. We also discussed the time complexity and Space Complexity of each approach. We would suggest you solve them to gain more confidence in these kinds of problems. These questions are asked during various coding contests as well as placement tests and thus are very important. 

We hope this blog has helped you enhance your knowledge of the Stock problem and Dynamic Programming. If you want to enhance more, then check out our blogs.

• Best time to buy and sell stock
• Best time to buy and sell stock II
• Best time to buy and sell stock III
• Best Time to Buy and Sell Stock IV
   

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others.

Happy Learning, Ninjas!