Dear reader, welcome to the article on the problem named "Buy And Sell Stocks with Cooldown - Infinite Transactions Allowed". It is the 4th problem in the series Buy & Sell Stock.
Important Links : Problem Link, Solution Video
Buy & Sell Stock - Cooldown
When you throw yourself out there great things happen. Just take this course blindly and dive into the world of programming starting from scratch.
~ Prajwal A.
Dear reader, welcome to the article on the problem named "Buy And Sell Stocks with Cooldown - Infinite Transactions Allowed". It is the 4th problem in the series Buy & Sell Stock.
Important Links : Problem Link, Solution Video
Note - There can be no overlapping transaction. One transaction needs to be closed (a buy followed by a sell) before opening another transaction (another buy). We cannot first buy 2 stocks and then sell them, i.e. states like "BBSS" are not allowed
Nobody will laugh at you, if you didn't know this! It is very trivial, but still, I want to let you know that you cannot sell a stock before buying it! You cannot have a state "SB".
Example:
Consider the array of days as : [1,2,3,0,2].
The maximum profit can be achieved by:
- Buying at day 0 = 1
- Selling at day 1 = 2
- Cooldown for day 2
- Buying at day 4 = 0
- Selling at day 5 = 2
Hence the profit = ((2 - 1) + (2 - 0)) = 3.
This problem is very similar to the previous problem where instead of cooldown, we had to take transaction fees into consideration. Here, we will need to maintain 3 states for each day.
Can you derive a relation for the states at day i, using the values of bsp state, ssp state and csp state at day i-1?
BSP State: If it is necessary to have one stock extra in our hand, then we have two options:
We will consider that option whichever gives us more profit (or less loss).
SSP State: If it is necessary to have to equal number of stocks bought and sold, then we have two options:
We will consider that option whichever gives us more profit (or less loss).
CSP State: If it is necessary to have to equal number of stocks bought and sold, and we have completed a cooldown of 1 day, then we have two options:
We will consider that option whichever gives us more profit (or less loss).
The only task left is to analyze the corner case.
Note: Please note that there can be negative value in any state, which represents we are at a loss. (Profit of -x is equivalent to loss of x).
At last, we will return the value of ssp state of the last day as our result, since it will contain the maximum profit with no extra stock left in our hand (no incomplete transaction) and it has taken into account all the n days.
Q) Why cannot we consider the bsp state of the last day as our result?
R)The bsp state of the last day cannot be considered as our result, because it has one incomplete transaction, because there is one stock extra in our hand, which is still left to be sold.
Q) Why cannot we consider the csp state of the last day as our result?
R) Please note that we need to cooldown only between selling a stock which we bought previously and buying a new stock. Thus, we need not cooldown after the last stock sold. Did you get the point of "Why to unnecessarily add one day of cooldown"?
Some Modifications in the logic to reduce Space Complexity
Uptil now, we have used three arrays of size n each. But, you can easily see that there is no need to store the states of all the previous days for the calculations. We just need the state of the immediate previous day ( (i - 1)^{th} previous day for i^{th} current day) and all the days before (i-1), i.e. days (i-2), (i-3), and so on, need not be stored.
Hence, we can replace our logic with 6 integer variables, three for previous day bsp, ssp and csp state, namely bstp, sstp and cstp , and other three variables for the current day bsp, ssp and csp state, namely nbstp, nsstp and ncstp.
Well, there will be a little difference in the implementation part, but, I expect from you that you can easily make these amendments accordingly.
Note: Before reading the Code, we recommend that you must try to come up with the solution on your own. Now, hoping that you have tried by yourself, here is the Java code.
java; true";
Java Code is written and explained by our team in the solution video.
Dry Run of the code using an example is taken and elaborated in the same video.
O(N)
Since, we are traversing through the array of n integers (representing days), and filling 3 states for each element, the time complexity will be O(3 * N) = O(N).
O(1)
Since we have replaced our logic of two arrays with just 6 integer variables, the space complexity will reduce from O(N) to O(1).
Q) If someone asks you to print the state in which you get the maximum profit, i.e. the sequence of the days in which stocks were bought and sold, then will you be able to adapt according to the problem requirements ?
R) Along with the maximum profit, we can also maintain a string (or an array) of the current bsp, ssp and csp state, the string will represent the sequence of stocks buy and sell upto the current day. Finally, we will print the resultant sequence which is stored in the ssp state of the last day.
Hope that you liked the article on "Buy And Sell Stock - with Cooldown - Infinite Transactions Allowed".
We have solved three problems on infinite transactions:
What Next? I should tell you that the next problem is not Infinite transactions with both transaction fee and cooldown. (It is very easy to club the questions).
Next problem will be the 5th problem in this series "Buy And Sell Stock - Two Transactions Allowed".
Subscribe to Pepcoding's youtube channel for more such amazing content on Data Structures & Algorithms and follow the resources available for all students in the resources section of Pepcoding's website.
You can suggest any improvements to the article on our telegram channel, or on the youtube channel's comment section.