Your explanation was really good. As far as constant space O(1) is concerned we can use state machine method to achieve it by using 3 variables for buy, sell & cooldown respectively.
Thank you for the explanation! After you explained the high level logic, I didn't even need to see your code and passed all my tests (I usually need high level understanding unless I lack the technical knowledge)
Here is better solution: C# int sold = 0; int hold = Int32.MinValue; int rest = 0; for (int i = 0; i < prices.Length; i++) { int prevSold = sold; sold = hold + prices[i]; hold = Math.Max(hold, rest - prices[i]); rest = Math.Max(rest, prevSold); } return Math.Max(rest, sold);
Hi All, Please find the time and space complexity of this solution below - Time complexity - O(n) Space Complexity - 0(n) **Here we are using 2D array (row = no. of elements in given array i.e n , column = 2 ) . So we can treat space complexity as O(n).**. Please comment if you can think a way to solve this question in constant space ? Also comment if you have any better way to solve this problem.
I think we can optimize this one by getting rid of the dp vector since we need to consider last two states. This practice is standard and I'm pretty sure you are aware of keeping two variables instead of an entire vector for storing two states. Anyway, kudos to you.
Instead of just filling up the table in a bottom up manner , You should have explained the recursive formula , how it is working and build the solution in a top down approach as they are easy to understand.
Great video Jayati, One question here : Why did you consider the day 0 holding a stock as -prices[0]. I mean dp[0][1] = -prices[0]. Why do we need to have a negative value of the price?
Hey Pankaj , since we bought the stock on day 0 ,and paid its price therefore it has to be subtracted from our profit.our profit on day 0 is 0 bucks , so 0 - price of stock on day 0 = -price[0]
dp represents max profit.. so if we have stock on 0 th day we have just bought the stock .. hence what ever the profit we get in the future will be selling price - cost price ... cost price is now prices[0] ... selling price we don't know yet.. where for we add -prices[0] so in the future we need to only add the selling price to get profit...
But how do you make a conclusion it can be solved using DP ? Can you make a iteration approach first and then recursive and then come to a conclusion .... ?
Hi, thanks for the video and I really like the clear explanation, but one thing I can't understand is the return value. why just return dp[len-1][0] instead of max{dp[len-1][0], dp[len-1][1]} ? How to guarantee that I always don't want to hold the stock on the last day? I may want to hold it on the last day if that gives me the best value?
Buying stock means you will spend the money . So assume if on day i you have x amount and on i + 1 you buy stock then on that day you will have x - ( cost of that stock ) amount left with you . If i+1 is last day then you will never buy a stock as you don't have any day left to sell it. So to ensure maximum profit you should not have any stock unsold.
I think your explanation lacks some basic info. So, in nutshell, what values do dp[i][0] and dp[i][1] have? And why are we just returning dp[-1][0], not max(dp[-1])??
Bad explanation, no one could ever come up with that dp equation by himself directly. Should have been better if you had built the solution recursively and then applied memoization.After the recursive solution is build then only we can write the dp equation.
![Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee [ Algorithm + Code Explained]](http://i.ytimg.com/vi/oVKaUeQsQJE/mqdefault.jpg)
![Leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee [ Algorithm + Code Explained]](/img/tr.png)
![Leetcode 123. Best Time to Buy and Sell Stock III [ Algorithm + Code Explained]](http://i.ytimg.com/vi/gVavspgEHyM/mqdefault.jpg)
![LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal [Solution + Code Explained ]](/img/n.gif)
I had watched about 2/3 videos about this question until I cam across yours, and finally understood it! Thank you so much!
Your explanation was really good. As far as constant space O(1) is concerned we can use state machine method to achieve it by using 3 variables for buy, sell & cooldown respectively.
Thank you for the explanation! After you explained the high level logic, I didn't even need to see your code and passed all my tests (I usually need high level understanding unless I lack the technical knowledge)
Here is better solution: C#
int sold = 0;
int hold = Int32.MinValue;
int rest = 0;
for (int i = 0; i < prices.Length; i++)
{
int prevSold = sold;
sold = hold + prices[i];
hold = Math.Max(hold, rest - prices[i]);
rest = Math.Max(rest, prevSold);
}
return Math.Max(rest, sold);
Hi All,
Please find the time and space complexity of this solution below -
Time complexity - O(n)
Space Complexity - 0(n)
**Here we are using 2D array (row = no. of elements in given array i.e n , column = 2 ) . So we can treat space complexity as O(n).**.
Please comment if you can think a way to solve this question in constant space ?
Also comment if you have any better way to solve this problem.
maam shoudnot the dp[0][0] = prices[0], if not please explain, i am really cnfused please!!! thanks
@@vibekdutta6539 how can you sell the stock at the 0th price on day 0?
i get the answer of my question,0th day selling a stock without buying one aint ppossible
I think we can optimize this one by getting rid of the dp vector since we need to consider last two states. This practice is standard and I'm pretty sure you are aware of keeping two variables instead of an entire vector for storing two states.
Anyway, kudos to you.
That was good... efficient code and well explained walk through.
Thanks for sharing. Very detailed explanation.
best explanation by far
One of the best videos I ever saw on this question !!
Thank you for nice explanation
Beautiful explanation
Crisp explanation! Looking forward to more.
bahaut badhiya ji... dil khush kar ditta aapne !!!
Good video. One small recommendation is to share the solution link that can viewed to revise them before the interviews
Thank you! It is an awesome explanation!
Instead of just filling up the table in a bottom up manner , You should have explained the recursive formula , how it is working and build the solution in a top down approach as they are easy to understand.
Great explanation. Easy to understand. Thanks!
Thanks for such an intuitive explanation
great explanation, thank you for sharing.
Great video Jayati, One question here : Why did you consider the day 0 holding a stock as -prices[0]. I mean dp[0][1] = -prices[0]. Why do we need to have a negative value of the price?
Hey Pankaj , since we bought the stock on day 0 ,and paid its price therefore it has to be subtracted from our profit.our profit on day 0 is 0 bucks , so 0 - price of stock on day 0 = -price[0]
dp represents max profit.. so if we have stock on 0 th day we have just bought the stock .. hence what ever the profit we get in the future will be selling price - cost price ... cost price is now prices[0] ... selling price we don't know yet.. where for we add -prices[0] so in the future we need to only add the selling price to get profit...
Very helpful, thank you
Nicely done.
Nicely explained!
Great explanation
Best solution !!!
Thank you! Amazing solution!
good video!
Well explained
Bravo on this video!
This was helpful mam can you please do more questions on dp?
But how do you make a conclusion it can be solved using DP ? Can you make a iteration approach first and then recursive and then come to a conclusion .... ?
Awesome got it thanks
Great explanation. Thank you!
Plz could you make a quesiton on regex solving in c++ using stl..
We could do it with constant space
wow, where have you been all this time?
Hi, thanks for the video and I really like the clear explanation, but one thing I can't understand is the return value.
why just return dp[len-1][0] instead of max{dp[len-1][0], dp[len-1][1]} ?
How to guarantee that I always don't want to hold the stock on the last day? I may want to hold it on the last day if that gives me the best value?
Buying stock means you will spend the money . So assume if on day i you have x amount and on i + 1 you buy stock then on that day you will have x - ( cost of that stock ) amount left with you . If i+1 is last day then you will never buy a stock as you don't have any day left to sell it. So to ensure maximum profit you should not have any stock unsold.
@@jayatitiwari444 Eva said Thank you!
9:22 you forget to handle the case when len == 2 && prices[0] == prices[1]
I think your explanation lacks some basic info. So, in nutshell, what values do dp[i][0] and dp[i][1] have? And why are we just returning dp[-1][0], not max(dp[-1])??
kuch samj nai aya lol
Bad explanation, no one could ever come up with that dp equation by himself directly. Should have been better if you had built the solution recursively and then applied memoization.After the recursive solution is build then only we can write the dp equation.
Very poor explaing.
going to some other video.