Coding Interview Question | Best time to Buy and Sell Stock | One, any number and max K Transactions
Vložit
- čas přidán 9. 07. 2024
- LeetCode and InterviewBit Links-
One transaction - leetcode.com/problems/best-ti...
www.interviewbit.com/problems...
Any number of transactions - leetcode.com/problems/best-ti...
www.interviewbit.com/problems...
K transactions - leetcode.com/problems/best-ti...
www.interviewbit.com/problems...
K = 2 transactions - leetcode.com/problems/best-ti...
www.interviewbit.com/problems...
The video includes following details-
0:00-0:55 - Problem statement
0:55-3:00 - One transaction question in detail
3:00-3:50 - Brute Force for one transaction
3:50-8:05 - Algo for one transaction
8:05-10:30 - Algo for any number of transactions
10:30-12:15 - Peak valley explanation for any number of transactions
12:15-13:20 - Dp visualisation for k transactions
13:20-13:50 - Initial conditions for k transactions
13:50-17:00 - Initial algo for k transactions
17:00-20:00 - Dry run of initial algo
20:00-21:15 - Complexity of Algo and scope of improvement
21:15-23:10 - Improvement of algo
23:10-30:00 - Dry run of final algo
30:00-31:40 - Optimization
Please Subscribe to my channel - / keertipurswani
LinkedIn - / keertipurswani
Instagram - keerti.purs...
Your explaining power and clarity of thought is excellent. Keep it up.
Thank you :)
I have a challenge for you Keerti, almost every solution in the internet talks about solving it iteratively. It doesn't explain how we all arrived at this iterative approach. Iterative approach is the last step in a DP solution. We first start with plain Recursion + Divide and Conquer, then see overlapping problems, then we memoize it, then we see that our problem's state changes on only two variables and we "transform" it into a iterative one.
Unfortunately directly explaining the iterative approach is like we need to "memorize" this approach. I am looking for the INTUITION behind it.
Thanks for taking the effort in making this video, I have some take aways from it.
Looking forward to your response.
Thank you,
A fan
Hi, thanks for your comment!
I try to discuss the intuition behind each problem.
Please do tell me what exactly did I miss. I would love to take up the challenge. I hope you have gone through the other dp videos as well :)
Last thing I want someone to do through my videos is to memoize the solution..
You definitely explained the intuition behind the iterative approach.
But the thing is, the iterative approach is a FINAL step in DP optimization.
It goes from Top Down (Recursive) ----> Then Memoize overlapping sub-problems ----> Then flip it upside down via bottom UP (Here there is no call stack, it's all iterative)
It's hard to explain on CZcams comments, but I hope we are getting somewhere on the same page?
Yes I am getting what you are saying but in an interview you don't have so much time. Getting the Intuition and being able to write dp solutions is my core purpose for the series.
If many people need it, I will surely make separate videos to cover memoization etc. Can't include in same video as most people prefer shorter videos and my videos are already long. I hope you understand what I am saying..
A similar discussion happened on my wildcard matching video :)
I am trying to follow approach that will help more number of people.
Thank you for your feedback! If there are more people who need this, I will definitely make videos covering it :)
@@KeertiPurswani Thank you Keerti *thumbs up*
Very helpful explanation, really helped to start from the simpler problems and work the logic to the trickiest one! Love the support you are giving to all of us while explaining really hard moments! Thank you SO MUCH for your hard work!! Keep it up!
Keerti, thank you so much for the best ever explanation! I finally understood the problem and was able to write the code. I have had trouble understanding the dynamic approach for k transactions. I tried various other explanations but I still couldn't figure it out. So glad to have found your channel!
you might be bored reading this, but its my responsibility to acknowledge the help you did by making a video on this, thank you so much.
Hello Keerti! Is there any way we can apply this optimization (maxDiff) to a recursive solution? I am more into recursive based dynamic programming solutions as I find them much more intuitive and it has paid me dividends! I was finding it difficult to implement this optimization in a recursive solution.
Found best explanation of this LeetCode question - out of all the videos of max K variation, this is by far the clearest.
Good explanation. In case of 1, 2, 3, 4, 5, 6 the profit of buying at 1 and selling at 6 is highest as we cannot buy and sell on the same day hence scenario of buying at 1 and selling at 2 and again buying at 2 and selling at 3 and so on is invalid. In this case peak and valley makes sense to maximize the profit, 1 is valley and 6 is peak.
The best video so far I have seen for Buy and Sell Stock problems. Thank you so much!
This helps a lot. A very good compilation.Thanks Keerti!!
Thanks Palak 😇
Thanks Keerti. Done an amazing job here :) Keep this up!
Thanks 😇😇
I watched all videos on this question but your explanation was the best among them. Keep up the awesome work!. It really helped me. Thank you for taking your time out and teaching us.
Great explanation! Thanks a lot!
Awesome. One video for all cases is a gold resource. Great explanations :)
I finally got my head around this problem today.
All thanks to you Keerti di.
Yay 😇😇
Wooah!!! Your explanation was awesome it went right into my head!!!! Thankyou
@Keerti, really nice explanation, keep doing more (variant - stock buy/sell
with transaction fee).
2 suggestions:
- intuitive variable names (arr -> prices, M->profit, 'M' vs 'm' at 16:29 how about 'm'->k to keep it simple)
- Please add git repo link for the solution and quick code walk-thru (2-3 min)
Will do! Thanks for your suggestion 😊
Really well explained! Thanks a lot!
😇😇
Thanks, a lot keerti, God Bless you. I was struggling to understand this problem from morning to evening I was not getting into my head. Finally, your explanation and way of teaching helped me to understand clearly without any doubts. Thanks a lot once again.
So glad I could help you ❤️
Omg such a nice explanation :)
This video is damn underrated!
Great explanation.. Keep posting such amazing video. Thanks a lot
Thank you ❤️ Hope you like other videos as well 😇
Am I only the one who thinks she could have explained better , well I learnt something so I do not have any regrets seeing this video
Just Loved the Explanation, Wanted more tutors like you :)
Thank you so much Pavan. Means a lot😇😇
Hii @Keerti Purswani
thank u for such a beautifull solution with great explaination ........... looking forward for the videos on Best time to Buy and Sell Stock with cool down and with transaction fee . I solved these questions but still many times confuse , I hope i can get some clear clarity with your beautifull way of explaining :)
Next level explanation .....Hats off!!
Thank you so much ❤️
you are really awesome explainer :)
good explanation! Thanks!
Glad you liked it!😇
Amazing Explanation. Keep it Up!
Thank you 😇😇
could not understand why maxDiff approach will work?
As simple as it can be, beautiful explanation. The same approach works for all variants. Can you take some more standard hard problems?
For sure, many coming up!!
best video explanation on yt for this problem
Thanks Rohit. Hope you like rest of the videos as well 😇
How do you come up with "maxDiff"? How did you derive maxDiff from m -> 0...j - 1?
Ye ques maine bohot pehle try kiya tha pr nhi huwa but aaj ek aur try diya but I was'nt able to solve.
Finally I got the approch.
Thanks for your effort
Thank you 🙂
This was about finding Maximum Profit. How to find Minimum Loss that the user can have?
Really good explenation
Quite enlightening! Can some one please provide this array for the future of any one company.
great explanation , keep it up :)
Thank you 😊😊
Liked the video. Would have been more intuitive if started with explaining the relevance of overlapping sub-prob and optimal sub-structure in this problem. I understand from comment section you are against doing memoization in the interviews but jumping directly to explaining optimised approach has high chance of people memoizing the solution itself :-) and find it hard to arrive at an approach when the question is tweaked in the interview. As with length of the videos, timestamps in the video description may help, if people wants to jump directly to final optimized solution. My dumb brain lost it when you started doing k=2. LOL. But still a great video. Myself a big fan of your catalan numbers video. Thanks for your efforts.
Amazing ✨👏🏻
Keep going...great explanations..🤗
Thank you 😇😇
GREAT EXPLANATION !!!!!!!!!!!
Thank you 😇
They only thing that went into my head is that you are making really good profits in stocks...O(paisa^paisa)
And please make videos for the other two variations as well. It will be really helpfull
Sure!!
Underrated channel
Please do help the channel grow by sharing it with your friends 😊
Rocked !!!
Thanks 😇
amazing!
Thanks 😇😇
well, at 7:12 you are saying we don't need to check that but that's wrong completely.You use else in place of else if it will be wrong bcoz its not necessary that arr[i]-min>profit always.
Didi code bhi daal dete to acha hota !!! I can see a million subscriber you tuber coming up ;)
nice explanation !!!!!!!!!!!!!
Thanks 🙂
Are we allowed to buy and sell on the same day?? I mean i bought the stock on day x @ 1 sold it @ day y @ 5 again buy the stock @ 5 and sold it on some day z @ 10 ??
Its like: buy (sell,buy) sell ... We are selling and then buying on the same day.. . is this allowed ... Because the question mentions it is not allowed but ur algorithm allows this... Help me !
Hi Ayush,
You can buy a stock on the same day after selling it
Otherwise it would have been mentioned that there is a cool down of 1 day and you can buy on next day only 😊
@@KeertiPurswani This doesn't seem right, why we will buy and sell the same day?
@@ajaysharma2007ym sell the previous stock and buy a new stock
Thanks for explanation.I have been going through many videos for this problem.But still I'm struggling for cool down.Can you explain it?
Sure, will do 😊
Once again, You should A+ for your explanations
Haha thanks 🤭🤭
it was helpful :)
So glad 😇
I like ur denim..which brand?
please explain the other two variations mam
Noted 😊
ig ,i saw her on linkedin O.o
Wouldn't it be k>=n/2 ??
Can you also create in Hindi
I know this is a problem but in the real world, it's not possible because no one knows tomorrow's price. 😊
Make variations of stock sell problem vidoes
Which variations?
@@KeertiPurswani one with cooldown , it's there on leetcode
Yes I have mentioned that in the end of video. One is with cooldown and one with transaction fees :)
Very nice explanation you covered all the scenario . Also no offense but its sometimes difficult to concentrate between you and the problem.
you are the problem.
It was an awesome explanation. But I have one doubt
GFG code snippet:
profit[t][i] = max(profit[t][i-1], price[i] + max(prevDiff, profit [t-1][i-1] - price[i-1])
where prevDiff is max(profit[t-1][j] - price[j]) for all j in range [0, i-2]
This thing I didn't understand, profit [t-1][i-1] - price[i-1]. Can someone clear my doubt like why profit[t-1][i-1] - price[i-1].
Abe tujhse kisi ne pucha ki code de faltu ka hero ban raha hai lodu😡😡😡
@@siwi_drake4703 Homie chill, I know your parents might use these words at your home but dont show your culture what your parent's taught you here in social media it gets viral dude.
It's like that , because of the formula , we need max of those values for optimization. Watch video again.
I think maxdiff should be M[i][m]-v[m] instead of M[i-1][m]-v[m] because former is giving correct answer while later is giving incorrect answer. plz see into it ma'am.
Depends on the question you are doing Divyanshu. If you can make buy after selling on the same day, it will be M[I][m]. If you can buy only one day after selling, it's M[I-1][m]
@@KeertiPurswani okay ma'am got it. Thanx for replying. Your videos are really helpful.
And I wanna ask something. Without knowing the problem from basic like recursion it's waste of learning. It's mostly like byhearting the problem. In interviews we can't explain clearly..My request is to make videos from basic
I have been explaining the logics. I hope noone thinks that is anywhere near to "byhearting" the problem. But yes, you are right and I am planning to cover recursion in coming videos 😊 My major worry initially was the length of videos. Already my videos are pretty long and I am sure if I add recursion, many people won't open them because everyone is short of time 😅
@@KeertiPurswani
Make the one video into parts and complete topic covers nearly 3-4 problems in leetcode. So it'll be very helpful if we understand from basics
@@ravitejachittela4370 this is the only video where I have covered multiple problems. Please checkout other dp problems on my channel as well. Even those videos are pretty long 😅
@@KeertiPurswani okay..your explanation is good. Once again thanks for making videos for us
Thank you @raviteja. It really means a lot to me ☺️ and I hope you didn't misunderstand what I was saying. I genuinely want people to understand the questions I do tutorials on 😅
Opps ... I thought its a stock market tutorial to buy and sell ... 🙄 it's different
🤭🤭
In case you want to check out content on stocks, my father has a channel on the same with the name - Kishore Purswani 😇😇
thank you mam
this question ist so dumb. in the Stockmarket is no Time Machine to see what the price will be in the future. so you just hope to buy low, but you will never ever know if you sell with the highest profit.