Best time to buy and sell stock with cooldown | Leetcode

This video explains the approach to solve the problem, best time to buy and sell stock with cooldown which is from leetcode 309.This is an extension for the problem best time to buy and sell stock 1 & 2.In this video,i have explained the approach to think about the solution for this problem and i have also shown how the given problem can be formulated as a recursion problem and how we can optimize it to solve the problem efficiently.In the second half of the video, i have explained the most efficient approach to solve this problem by making use of the states a person can be on a given day.There are only 3 states possible and so i have shown how the problem can be formulated into a state machine problem.This is the best approach which takes just O(N) time.This approach is also a dynamic programming approach.The space complexity can be reduced to O(1) because we just need to remember the previous day state a person can be.So, this can be done using 3 variables because we have just 3 possible states.At the end of the video, i have explained the code walkthrough of the given problem both by recursion + memoization and also state machine dynamic programming.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINK:-
Best Time to buy & sell stock 2: • Best time to buy and s...

[@theghostwhowalk]

Liked the State diagram way!

[@techdose4u]

I personally liked it too. So, I skipped tabulation DP approach.

[@abhishekks6782]

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 🙏

[@techdose4u]

Welcome bro :)

[@vvk6260]

@@techdose4u who came up with this, that is amazing..

[@PRANAVMAPPOLI]

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😻🖤

[@sameekshabhatia3200]

This was so clear.Very well explained .Thank you so much.

[@yuvrajsinghrathore4919]

I was thinking of memoization technique but your state diagram method is much optimized. Loved it

[@BaishaliGhosh13]

Super explanation with great clarity. Learnt a new technique. Thanks!

[@techdose4u]

Welcome :)

[@trineshreddybs842]

keep sharing your knowledge of problem solving SIR.It will be very helpful for us

[@drishtdyumnshrivastava5313]

this really made the concept crystal clear
thank you...... as i always say ur channel is very underrated..

[@harshitsharma7871]

Very well explained. Appreciate it.

[@code_life4835]

Great Explanation! Thanks a lot, Sir

[@techdose4u]

Welcome

[@VarunMittal-viralmutant]

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 ?

[@jaden2582]

Best illustration on three-state approach on youtube for this problem.

[@techdose4u]

Thanks :)

[@piyushgoyal9633]

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

[@andriidanylov9453]

Great job. Appreciate

[@kunalsoni7681]

Great video 😇
Thank you so much to explain always in very deeply

[@techdose4u]

Welcome :)

[@karankhara1312]

Thanks for the great explanation!

[@techdose4u]

Welcome 😊

[@ankitgoyal34]

Thank you for explanation!!

[@techdose4u]

Welcome :)

[@rishabhgoyal8110]

God bless you Man!

[@techdose4u]

❤️

[@rishabh2055]

Good insightful Explanation 👍

[@techamet428]

like usual.. beautifully explained 🔥🔥

[@techdose4u]

Thanks :)

[@pleasesirmorevideos4684]

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

[@techdose4u]

Okay sure

[@prateeksinghal630]

I loved the memoized code !!

[@techdose4u]

Thanks :)

[@neerajchoudhary3709]

bhai bhai, kya baat hai, thanks man

[@prasad.patil12]

Great explanation 👍

[@666Imaginative]

thank you so much sir

[@sumonchatterjee5337]

awesome explanation both with dp and state diagram

[@techdose4u]

Thanks

[@anandbangad2966]

In the state diagram how are we considering the cool off days, what if the cool of day is more than 1 ?

[@sharmamukul938]

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]}.

[@surabhisingh9956]

Wow, such a good explanation

[@techdose4u]

Thanks :)

[@K_EC_AushoRoup]

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.

[@techdose4u]

Nice 😊

[@trishulcurtis1810]

Whats the time complexity of recursive memoization ?

[@shaziasamreen8584]

Great explaination 👏

[@techdose4u]

Thanks :)

[@anushkagupta5917]

how is the state approach taking cooldown into account?

[@devilkanu4890]

Can anyone explain how the state machine dynammic programming following the given cooldown constraint?

[@suyashlokhande1981]

simply awsome

[@techdose4u]

Thanks

[@animeshjain4594]

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?

[@vishalverma920]

what is the time complexity of recursive solution after memoization ??

[@siddharthsaxena6495]

great explanation

[@techdose4u]

Thanks

[@junxuchen2851]

The state machine algorithm is incredible... Can't imagine how to come up an algorithm like this

[@techdose4u]

It's very difficult 😅

[@amitavamozumder73]

please make a video on how to identify state machine problems.

[@mystryb345]

Wow what a explanation sir finally i understood all type problem of it..Sir if possible make video on at max K transactiom

[@techdose4u]

Sure :)

[@slimysnail6071]

What is the time complexity for the recursion approach?

[@mishikaraj5153]

well explained Sir!

[@techdose4u]

Thanks :)

[@VivekMishra-hd7mg]

very well explained

[@techdose4u]

Thanks

[@amanrai8010]

What will be the complexity of memo solution

[@pramodsinghyadav7580]

great explanation.I was looking for memoziation method which code is explained here nicely

[@techdose4u]

Thanks

[@Arunkumar-pg8kx]

What if cooldown period is 2 days (n days)

[@tushardhote6393]

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.

[@techdose4u]

Try to seebthe memoization + recursion code for cooldown. I have explained where you need to make change to solve for D-days.

[@tushardhote6393]

@@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?"

[@amchourasia]

Perfect

[@techdose4u]

Thanks :)

[@deepakpoojari9019]

Thanks man

[@techdose4u]

Welcome

[@shubhamgiri2840]

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

[@ashishg656]

Great :)

[@techdose4u]

Thanks

[@shushantgaur9420]

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?

[@techdose4u]

You should watch the next version of this problem and my solution

[@shushantgaur9420]

@@techdose4u all right👍. Although I was going to watch it anyways, cause it's really good content :)
Thanks again

[@techdose4u]

@@shushantgaur9420 nice :)

[@lobsanggyatso6280]

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

[@techdose4u]

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.

[@kunalsoni7681]

@@techdose4u thanking you 😇

[@prateeksinghal630]

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 !!

[@vikasg5395]

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]

You need total 4 variables to remeber state of sold. 3 rows 2 cols is also fine.

[@vikasg5395]

@@techdose4u thanks for the quick response

[@techdose4u]

Welcome

[@subhamtripathi1997]

sorry , but didnt we skip the "2" in the second valley?

[@pleasesirmorevideos4684]

sir what if cooldown is of d days it is hard to visualise with states although very easy with recursive + memo

[@techdose4u]

Yep. With d-days cooldown, you will stay at noStock state for atleast d-days when you reach there from Sold state.

[@vishalmishra9549]

@@techdose4u So like the present soldstate value be equal to past one and only nostock and inhand state will get changed?

[@vishalmishra9549]

@@techdose4u so the soldstate value will be const for d-1 days?

[@financewithsom485]

the 2nd method is only for cooldown of 1 day right??

[@techdose4u]

Yes. If you can modify the state machine then it may also work for K days :)

[@jayeshmarathe7678]

Was the recursive code difficult to understand or its just me ☹️

[@gauravagarwal8592]

Why you say K+1 instead of K for the K cool Down period ? Can someone explain please?

[@shahperzia2111]

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

[@gauravagarwal8592]

@@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.

[@shahperzia2111]

@@gauravagarwal8592 yes for k=1 with can buy i+2 th day

[@ankurrohilla4655]

sir how the conditions changes when the cooldown period is not 1 lets say it's 5?

[@techdose4u]

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.

[@ankurrohilla4655]

@@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 ?

[@mvee]

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);

}
}

[@techdose4u]

Thanks

[@shushantgaur9420]

@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.

[@mvee]

@@shushantgaur9420 ohh, I see what you mean. Thank you for the clarification!

[@shushantgaur9420]

@@mvee no problem bro:)

[@abhinavmishra7617]

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?

[@techdose4u]

Esko skip krdo. Baad mein samajh aa jaega. Eske pehle wale videos dekhlo.

[@abhinavmishra7617]

dekh chuka hu...apne isme achcha nahi smjhaya h

[@techdose4u]

Kaunse area ko achhe se nhi btaya bta do. Firr agli baar se usko improve krunga.

[@SumitVerma-ln5nz]

Me to my Father: Should we invest in crypto-currency?
My Father: @27:37

[@vaishalirathore3723]

how is the state approach taking cooldown into account?

[@054_heenaahmed8]

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.