DAY 22 - Best Time to Buy and Sell Stock II

Hey Guys! Nayan here and this is the 22nd day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here.

Let's get right to the problem. This is a continuation of problem on day 5 and it would be much easier to understand if you have read my previous articles first.

DAY 22 Problem: Best Time to Buy and Sell Stock II

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Examples:

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

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

Intuition:

• Okay so, let's take our time understanding the question first and then we will proceed with our approaches.
• The question demands us to maximize the profit of buying and selling stocks. The trick here is that we can sell a stock and then buy it again. We can but it even on the main day itself as well.
• Let's note down our observations and then proceed.
• Observation 1: This is different from Buy and Sell Stock 1 because we can buy as many times and sell any times. The only condition being we must sell the stock before buying again.
• This leaves us down to two options. It's to either buy the stock or sell the stock. But We Must also know if we can even buy the stock or if we can sell it. You can't sell without buying and can't buy again without selling.
• So Let's follow a recursive approach where we try out all possibilities and return the max profit we can get.

Approach: Recursion + Memoization

• Step 1. Express the utility function parameters. Simply identify the things we will need and things that we need to keep track off at every single call of the function.
• Obviously we will have to traverse the array, so an index iterator, one variable to keep the count if we canBuy or not and the prices list for the calculation of profit.
• Step 2. Establish the base case: Let's start from the 0th index here. At the end we will reach index == size of the array and hence we won't need the array anymore, so we return 0.
• Step 3. Recursive Relation: Okay so as discussed we have to keep count if we can buy or not.
• Say we can buy, then we have two options either to buy or not to buy. Read this again. We don't necessarily have to buy and can simply move on.
• So, we assign a variable profit and we take the maximum value from both and assign it to profit.
• Similarly we can either sell or we can not, so we do the same for canBuy = false or if canBuy is false(it means canSell is true but we don't need two variables for this).

Take a look at code for better understanding.

class Solution {
public:
    int util(int index, vector<int>& prices, int n, int canBuy){
        //base case
        if(index == n) return 0;
        //two options either to buy and sell. 
        //Also must maintain if we are eligible to buy or sell using canBuy.
        int profit = INT_MIN;

        if(canBuy == 1){
            profit = max(-prices[index] + util(index+1, prices, n, false), util(index+1, prices, n , true));
        }
        else{
            profit = max(prices[index] + util(index+1,prices,n,true), util(index+1,prices,n,false));
        }

    return profit;
    }
    int maxProfit(vector<int>& prices) {
        return util(0,prices, prices.size(), 1);

    }
};

Since this is just basic recursion, we will have exponential time complexity and hence this is not a viable approach for extreme test cases.

We can memoize it using DP and lower the time complexity.

We simply need to make a dp array that keeps count of index and canBuy as that is the ever changing thing here.
We store the answers in our dp array and call it from that to reduce Time Comp.

Code:

class Solution {
public:
    int util(int index, vector<int>& prices, int n, int canBuy, vector<vector<int>>& dp){
        //base case
        if(index == n) return 0;
        if(dp[index][canBuy] != -1) return dp[index][canBuy];
        //two options either to buy and sell. 
        //Also must maintain if we are eligible to buy or sell using canBuy.
        int profit = INT_MIN;

        if(canBuy == 1){
            profit = max(-prices[index] + util(index+1, prices, n, false,dp), util(index+1, prices, n , true,dp));
        }
        else{
            profit = max(prices[index] + util(index+1,prices,n,true,dp), util(index+1,prices,n,false,dp));
        }

    return dp[index][canBuy] = profit;
    }
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
         vector<vector<int>> dp(n , vector<int>(2,-1));
        return util(0,prices, n, 1,dp);

    }
};

Complexity Analysis:

Time Complexity: O(N*2)
Space Complexity: O(N*2) + O(N). Extra space due to recursion.

We can convert this solution into a bottom up approach/tabulation to reduce the space complexity even further.

We will need to reestablish our base case for this and store it in dp array.

We will also traverse the dp using two for loops and follow the recursive relation but for DP to convert.
Read the code for better understanding.

Code:

int maxProfit(vector<int>& prices) {
        int n = prices.size();
         vector<vector<int>> dp(n+1 , vector<int>(2,0));
         //tabulation
        int profit = INT_MIN;
         //base case doesn't need to  be written as already initialized as 0
         //commented out the base case
         //dp[n][0] = dp[n][1] = 0;
         for(int index = n-1; index >= 0; index--){
             for(int canBuy = 0; canBuy <=1; canBuy++){
                 if(canBuy == 1){
                     profit  = max(-prices[index] + dp[index+1][0], dp[index+1][1]);
                 }
                 else{
                     profit = max(prices[index] + dp[index+1][1] , dp[index+1][0]);
                 }
                 dp[index][canBuy] = profit;

             }
         }

    return dp[0][1];
    }

Complexity Analysis:

Time Complexity: O(N*2)
Space Complexity: O(N*2). Extra space due to recursion removed using tabulation.

We can further space optimize this solution because at any moment we only require 2 things. The last 2 values of dp[][canBuy].
This forms the next two values and consequently like that. We don't need the whole dp array to store the values and hence we do exactly that.

Code:

int maxProfit(vector<int>& prices) {
        int n = prices.size();
         vector<int> ahead(2,0);
         vector<int> curr(2,0);
         //tabulation
        int profit = INT_MIN;
         //base case doesn't need to  be written as already initialized as 0
         //commented out the base case
         //dp[n][0] = dp[n][1] = 0;
         for(int index = n-1; index >= 0; index--){
             for(int canBuy = 0; canBuy <=1; canBuy++){
                 if(canBuy == 1){
                     profit  = max(-prices[index] + ahead[0], ahead[1]);
                 }
                 else{
                     profit = max(prices[index] + ahead[1] , ahead[0]);
                 }
                 curr[canBuy] = profit;

             }
             ahead = curr;
         }

    return ahead[1];
    }

Complexity Analysis:

Time Complexity: O(N*2)
Space Complexity: O(1). Constant space as we only used 2 arrays of size 2 which is 4.

Thanks for reading. Feedback is highly appreciated.