DAY 23 - Best Time to Buy and Sell Stock III

Hey Guys! Nayan here and this is the 23rd 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 22 and it would be much easier to understand if you have read my previous articles first.

Problem: Best Time to Buy and Sell Stock III

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

Find the maximum profit you can achieve. You may complete at most two transactions.

You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example:

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

Intuition : Recursion + Memoization

• In this question a new constraint has been added to us. If you have read my previous article, we already have 2 parameters which are changing in this question.
• The first being index that we are traversing and second to maintain a variable that tell us if we can buy the stock or not.
• Hence we will name this new variable trns.
• What does transaction mean in this question?
• To put it simply buying and selling a stock is one transaction.
• This means unlike the last question where we could buy the stock and sell it as much as we would like, that is not the case here.
• Hence we must maintain a parameter for this as well.
• Rest all of our approach shall remain the same. ## Approach:
• 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. In a case where we have reached the end of our transactions we also 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). At every sell we do, we decrease the transaction by one.

Code:

int getAns(vector<int>& Arr, int n, int ind, int canBuy, int trns , vector<vector<vector<int>>>& dp ){

    if(ind==n || trns ==0) return 0; //base case

    if(dp[ind][canBuy][trns ]!=-1)
        return dp[ind][canBuy][trns];

    int profit;

    if(canBuy){// We can canBuy the stock
        profit = max(0+getAns(Arr,n,ind+1,1,trns ,dp),
                    Arr[ind] + getAns(Arr,n,ind+1,0,trns -1,dp));
    }

    if(canBuy == 0){// We can sell the stock
        profit = max(0+getAns(Arr,n,ind+1,0,trns ,dp), 
                    -Arr[ind] + getAns(Arr,n,ind+1,1,trns ,dp));
    }

    return dp[ind][canBuy][trns ] = profit;
}


int maxProfit(vector<int>& prices)
{
    int n = prices.size();
    // Creating a 3d - vector of size [n][2][3]
    vector<vector<vector<int>>> dp(n,
                                    vector<vector<int>> 
                                            (2,vector<int>(3,-1)));

    return getAns(prices,n,0,0,2,dp);

}

Complexity Analysis:

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

To eliminate the extra recursion stack space, we reverse the approach and use tabulation.

Tabulation Approach:

We express the base cases and store them pre our traversion in DP.
Then we traverse using 3 for loops applying the same recursion logic and storing it in dp.

Code:

int maxProfit(vector<int>& prices)
{
    int n = prices.size();
    // Creating a 3d - dp of size [n][2][3]
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>> (2,vector<int>(3,0)));
     // base cases(only needed if we don't initialize the dp as 0)
    //  for(int buy = 0; buy < 2; buy++){
    //     for(int trans = 0; trans < 3; trans++){
    //         dp[n][buy][trans] = 0;
    //      }
    //  }
    //  for(int idx = 0; idx <=n; idx++){
    //      for(int buy = 0; buy < 2; buy++){
    //          dp[idx][buy][0] = 0;
    //      }
    //  }
    int profit;
    for(int ind = n-1; ind>=0; ind--){
        for(int canBuy = 0; canBuy<=1; canBuy++){
            for(int trans=1; trans<=2; trans++){

                if(canBuy==0){// We can canBuy the stock
                    dp[ind][canBuy][trans] = max(0+dp[ind+1][0][trans], 
                                -prices[ind] + dp[ind+1][1][trans]);
                 }

                if(canBuy==1){// We can sell the stock
                    dp[ind][canBuy][trans] = max(0+dp[ind+1][1][trans],
                                prices[ind] + dp[ind+1][0][trans-1]);
                }
            }
        }
    }


    return dp[0][0][2];

}

Complexity Analysis:

Time Complexity: O(N*2*3)
Space Complexity: O(N*2*3).

We can further space optimize it using only 2 arrays of size 6.

This is because if closely observe that at every recursion call our dp[index][canBuy][trans] depends on this:

dp[index][canBuy][trans] = max(dp[index+1][canBuy][trans], dp[index+1][!canBuy][trans])

Hence we can eliminate the extra space used for storing index and we can simply store it one time and then our value is dependent on other two parameters.

Approach

• Initialize two vector> ahead and curr with 0.
• We replace dp[ind] with cur and dp[ind+1] with ahead in our tabulation code.

Code:

class Solution {
public:
int maxProfit(vector<int>& prices)
{
    int n = prices.size();

    vector<vector<int>> ahead(2,vector<int>(3,0));
    vector<vector<int>> curr(2,vector<int>(3,0));
    int profit;
    for(int ind = n-1; ind>=0; ind--){
        for(int canBuy = 0; canBuy<=1; canBuy++){
            for(int trans=1; trans<=2; trans++){

                if(canBuy==0){// We can canBuy the stock
                    curr[canBuy][trans] = max(0+ahead[0][trans], 
                                -prices[ind] + ahead[1][trans]);
                 }

                if(canBuy==1){// We can sell the stock
                    curr[canBuy][trans] = max(0+ahead[1][trans],
                                prices[ind] + ahead[0][trans-1]);
                }
            }
        }
        ahead = curr;
    }


    return ahead[0][2];

}
};

Complexity Analysis:

Time Complexity: O(N*2*3)
Space Complexity: O(1)

Thanks for reading. Feedback is highly appreciated.