I have one word for you. You are "GENIUS", thank you so much sir for creating this kind of wonderful contents and helping many students and aspirants like me. I am out of words 🙏
You know what sir, I have solved this question by Recursion + Memoization (i.e., DP) but I came to your channel just for fun, and I Saw there is a Thumbnail saying Machine State Diagram approach for this question. And, Now I got learned 2 new Approaches => Valley peak + State machine algorithms. Previously I have used state diagram only in my ECE course. Thanks. I learned something new.
You greatly analyzed the vietnam dude discussing this finite state diagram.I find it very difficult to understand.I think it need a lot of work to understand that.Thank you for making us better understand by taking in depths of what other person told
Thanks for the great video. I have 1 doubt in the state machine approach though, is going from "sell" ---> "no stock" state implicitly considering the "cooldown" ? Since we don't talk about the cooldown at all while using the state machines, I got confused where that is coming into picture. If there was no cooldown, then also the state machine approach can be used ?
Sir, Super explanation with great clarity. Learnt a new technique. But in State transition I'm getting how you are tackling cooldown corner case and how can we apply this for d-days? If possible then please explain..would be of great help.
Great explanation .... But I am still not getting in state diagram method where we took the cooldown in consideration .... I tried with many examples though it is giving the right answer but how?
Awesome approach, especially second one. But @TECH DOSE I'm still not getting how we are solving the cool-down period of 1 day here. Maybe because it's specially for one day period... Maybe, can you explain about 3 days of cooldown with state machine?
I believe in that case , we will have only change the way we compute the values of states which are directly linked to the selling state , i.e, we will have to modify the way we calculate inHand state as now : inHand[i] = MAX{inHand[i-1] , sell[i-k]}.
Great Video Man! Here's the state machine algorithm in O(1) space (no arrays): class Solution { public int maxProfit(int[] prices) { int sell = 0; int noStock = 0; int inHand = Integer.MIN_VALUE; for(int price : prices){ int temp = sell; // 0 // For in hand, we can either maintain or we buy inHand = Math.max(inHand, noStock - price); sell = Math.max(sell, inHand + price); noStock = Math.max(temp, noStock); } return Math.max(noStock, sell);
@Michael Vandi How about we first find (Inside for loop) Temp= inhand; Inhand=max(nostock- price[i], inhand); Nostock= max(nostock, sell); Sell= temp+ price[I]; Reason: at 18:45 @TECH DOSE explained that you cannot remain in the same state for more than one day.... But according to the upper code you are assuming the max( previous day, and the current value). For example price[5]= {1, 2, 3, 0, 2}; (same example as tech dose) The values of fourth day of selling would be -1 because we are buying on first day and selling on 4 day... But according to the above code 4th day value is calculated by max( sell, inhand+ price[i]) that would give us 2 meaning we didn't sell on the fourth day but the 3rd. Or you can say that means you are considering the case where you sell on the third day and on the fourth day as well. Although it might not change the end result but I felt like telling you.
Hey ! I really liked your videos and and how explain the concepts. Can u put another variant of this problem where there can be multiple transactions on a single day (like buying on 2 consecutive days and selling both of them together on one day or 2 different days). It would be very kind of u if u could help me in this
Keep practicing. It's difficult to master DP. You need to be patient and keep practicing. If was easy then everyone would master it. Keep patience and practice. You will improve.
Don't focus on bottom-up dp too much!! If you can write the correct recursive code for the problem then you are on the right track !! Just try to learn how to memoize the simple recursive code as it is just adding 3-4 lines to your code and it gives the same time complexity as the bottom-up code using tabulation. Once you are able to write the memoized code then it's just a few steps more to convert that into the iterative approach using bottom-up dp !!
because if say k=0; this will mean you are buying and selling same day but it is not possible , so in general you have to use +1 and here you also have k cooldown days , so k+1
@@shahperzia2111 K is the cool down period it means once u sold the stock u cant buy on next day . u will have to skip one day . so in the case of k =1 we have to skip 2 days will that be okay. kindly correct me if understanding is wrong.
How do we reduce the space complexity from o(n) to just 3 variables? We need at least 3 rows x 2 columns. I am I missing something? (State diagram based sol)
@@techdose4u sir if we are going with second approach with cooldown period 5 ... we have to compare the current day scenario with the curr-5 days . sir , am I correct or not ?
in the state approach , in hand state is not followed by sold state, that is we are not buying stock immediately after selling it. Hence cooldown is taken into account.
I have read leetcode best answer 4-5 times to understand the diagram methoad and failed. But this single video make it all cristal clear😻🖤
I have one word for you.
You are "GENIUS", thank you so much sir for creating this kind of wonderful contents and helping many students and aspirants like me. I am out of words 🙏
Welcome bro :)
@@techdose4u who came up with this, that is amazing..
You know what sir, I have solved this question by Recursion + Memoization (i.e., DP) but I came to your channel just for fun, and I Saw there is a Thumbnail saying Machine State Diagram approach for this question. And, Now I got learned 2 new Approaches => Valley peak + State machine algorithms. Previously I have used state diagram only in my ECE course. Thanks. I learned something new.
Nice 😊
Whats the time complexity of recursive memoization ?
I was thinking of memoization technique but your state diagram method is much optimized. Loved it
great explanation
Thanks
You greatly analyzed the vietnam dude discussing this finite state diagram.I find it very difficult to understand.I think it need a lot of work to understand that.Thank you for making us better understand by taking in depths of what other person told
Liked the State diagram way!
I personally liked it too. So, I skipped tabulation DP approach.
Thanks for the great video. I have 1 doubt in the state machine approach though, is going from "sell" ---> "no stock" state implicitly considering the "cooldown" ?
Since we don't talk about the cooldown at all while using the state machines, I got confused where that is coming into picture. If there was no cooldown, then also the state machine approach can be used ?
Sir, Super explanation with great clarity. Learnt a new technique.
But in State transition I'm getting how you are tackling cooldown corner case and how can we apply this for d-days?
If possible then please explain..would be of great help.
Try to seebthe memoization + recursion code for cooldown. I have explained where you need to make change to solve for D-days.
@@techdose4u
Okay fine for D-days
Sorry it was mistyped.
My query was "In State transition I'm not getting how are you tackling cooldown corner case?"
Best illustration on three-state approach on youtube for this problem.
Thanks :)
this really made the concept crystal clear
thank you...... as i always say ur channel is very underrated..
Thanks for the great explanation!
Welcome 😊
Wow what a explanation sir finally i understood all type problem of it..Sir if possible make video on at max K transactiom
Sure :)
The state machine algorithm is incredible... Can't imagine how to come up an algorithm like this
It's very difficult 😅
Wow, such a good explanation
Thanks :)
that dp state diagram was so well explained sir. it will be so good if you cover these types of videos on dp. thanks again sir for your efforts
Okay sure
please make a video on how to identify state machine problems.
Super explanation with great clarity. Learnt a new technique. Thanks!
Welcome :)
keep sharing your knowledge of problem solving SIR.It will be very helpful for us
awesome explanation both with dp and state diagram
Thanks
Great explanation .... But I am still not getting in state diagram method where we took the cooldown in consideration .... I tried with many examples though it is giving the right answer but how?
Awesome approach, especially second one.
But @TECH DOSE I'm still not getting how we are solving the cool-down period of 1 day here. Maybe because it's specially for one day period... Maybe, can you explain about 3 days of cooldown with state machine?
You should watch the next version of this problem and my solution
@@techdose4u all right👍. Although I was going to watch it anyways, cause it's really good content :)
Thanks again
@@shushantgaur9420 nice :)
In the state diagram how are we considering the cool off days, what if the cool of day is more than 1 ?
I believe in that case , we will have only change the way we compute the values of states which are directly linked to the selling state , i.e, we will have to modify the way we calculate inHand state as now : inHand[i] = MAX{inHand[i-1] , sell[i-k]}.
God bless you Man!
❤️
great explanation.I was looking for memoziation method which code is explained here nicely
Thanks
simply awsome
Thanks
Great job. Appreciate
Great Video Man! Here's the state machine algorithm in O(1) space (no arrays):
class Solution {
public int maxProfit(int[] prices) {
int sell = 0;
int noStock = 0;
int inHand = Integer.MIN_VALUE;
for(int price : prices){
int temp = sell; // 0
// For in hand, we can either maintain or we buy
inHand = Math.max(inHand, noStock - price);
sell = Math.max(sell, inHand + price);
noStock = Math.max(temp, noStock);
}
return Math.max(noStock, sell);
}
}
Thanks
@Michael Vandi
How about we first find
(Inside for loop)
Temp= inhand;
Inhand=max(nostock- price[i], inhand);
Nostock= max(nostock, sell);
Sell= temp+ price[I];
Reason: at 18:45 @TECH DOSE explained that you cannot remain in the same state for more than one day.... But according to the upper code you are assuming the max( previous day, and the current value).
For example price[5]= {1, 2, 3, 0, 2}; (same example as tech dose)
The values of fourth day of selling would be -1 because we are buying on first day and selling on 4 day...
But according to the above code 4th day value is calculated by max( sell, inhand+ price[i]) that would give us 2 meaning we didn't sell on the fourth day but the 3rd.
Or you can say that means you are considering the case where you sell on the third day and on the fourth day as well.
Although it might not change the end result but I felt like telling you.
@@shushantgaur9420 ohh, I see what you mean. Thank you for the clarification!
@@mvee no problem bro:)
Very well explained. Appreciate it.
Great Explanation! Thanks a lot, Sir
Welcome
bhai bhai, kya baat hai, thanks man
Good insightful Explanation 👍
What is the time complexity for the recursion approach?
Hey ! I really liked your videos and and how explain the concepts. Can u put another variant of this problem where there can be multiple transactions on a single day (like buying on 2 consecutive days and selling both of them together on one day or 2 different days). It would be very kind of u if u could help me in this
I loved the memoized code !!
Thanks :)
how is the state approach taking cooldown into account?
This was so clear.Very well explained .Thank you so much.
what is the time complexity of recursive solution after memoization ??
Great video 😇
Thank you so much to explain always in very deeply
Welcome :)
Thank you for explanation!!
Welcome :)
Great explaination 👏
Thanks :)
very well explained
Thanks
thank you so much sir
sorry , but didnt we skip the "2" in the second valley?
Perfect
Thanks :)
Great explanation 👍
well explained Sir!
Thanks :)
the 2nd method is only for cooldown of 1 day right??
Yes. If you can modify the state machine then it may also work for K days :)
Sir can u give me some tip on dp , I can solve problem in recursion and but when it come to dp then I always stuck specially bottom-up
Keep practicing. It's difficult to master DP. You need to be patient and keep practicing. If was easy then everyone would master it. Keep patience and practice. You will improve.
@@techdose4u thanking you 😇
Don't focus on bottom-up dp too much!!
If you can write the correct recursive code for the problem then you are on the right track !!
Just try to learn how to memoize the simple recursive code as it is just adding 3-4 lines to your code and it gives the same time complexity as the bottom-up code using tabulation.
Once you are able to write the memoized code then it's just a few steps more to convert that into the iterative approach using bottom-up dp !!
What if cooldown period is 2 days (n days)
like usual.. beautifully explained 🔥🔥
Thanks :)
Why you say K+1 instead of K for the K cool Down period ? Can someone explain please?
because if say k=0; this will mean you are buying and selling same day but it is not possible , so in general you have to use +1 and here you also have k cooldown days , so k+1
@@shahperzia2111 K is the cool down period it means once u sold the stock u cant buy on next day . u will have to skip one day . so in the case of k =1 we have to skip 2 days will that be okay. kindly correct me if understanding is wrong.
@@gauravagarwal8592 yes for k=1 with can buy i+2 th day
What will be the complexity of memo solution
Can anyone explain how the state machine dynammic programming following the given cooldown constraint?
Thanks man
Welcome
How do we reduce the space complexity from o(n) to just 3 variables? We need at least 3 rows x 2 columns. I am I missing something? (State diagram based sol)
You need total 4 variables to remeber state of sold. 3 rows 2 cols is also fine.
@@techdose4u thanks for the quick response
Welcome
Was the recursive code difficult to understand or its just me ☹️
sir how the conditions changes when the cooldown period is not 1 lets say it's 5?
Then try to identify where I used 1. You can simply change the recursion jump size. I have explained in the code, where to change.
@@techdose4u sir if we are going with second approach with cooldown period 5 ... we have to compare the current day scenario with the curr-5 days . sir , am I correct or not ?
Great :)
Thanks
sir what if cooldown is of d days it is hard to visualise with states although very easy with recursive + memo
Yep. With d-days cooldown, you will stay at noStock state for atleast d-days when you reach there from Sold state.
@@techdose4u So like the present soldstate value be equal to past one and only nostock and inhand state will get changed?
@@techdose4u so the soldstate value will be const for d-1 days?
Me to my Father: Should we invest in crypto-currency?
My Father: @27:37
sir apne bilkul achcha nhi smjhaya is video me in comparison to al lyour other videos....kuchh samajh me nahi aya... what to do now?
Esko skip krdo. Baad mein samajh aa jaega. Eske pehle wale videos dekhlo.
dekh chuka hu...apne isme achcha nahi smjhaya h
Kaunse area ko achhe se nhi btaya bta do. Firr agli baar se usko improve krunga.
how is the state approach taking cooldown into account?
in the state approach , in hand state is not followed by sold state, that is we are not buying stock immediately after selling it. Hence cooldown is taken into account.