Thank you very much for such a wonderful explanation.Intuition development is very Important rather than coding and learning formula for this problem and you have explained it in depth with appropriate examples. Please keep making videos like these.
i should take max(profit, left[i]+right[i]) . if we take left[i-1] we're excluding a fact that ith element may be the maximum of left subarray and minimum of right subarray.... in that case. transaction where we sell on ith day while we bought from a day on left, is ignored. and if we have to sell and buy on same day... that's same as holding it, because left subarray ensures that we've already purchased before we're trying to sell. check for the input.. 1 2 3 4 5 . now consider 3 as pivot.. profit left = 1, and profit right = 5-3 = 2.. total profit = 3... but max profit is 4. 5-1.
I think its somewhat complicated to explain but you explained well ! here is a easy approach : class Solution { public int maxProfit(int[] p) { int pr1=0; int pr2=0; int mn1=Integer.MAX_VALUE; int mn2=Integer.MAX_VALUE; for(int i=0;i
I think the string operation glossed over in the middle is actually O(1) (since the length of the string would be constant) as it's just concatenating 3 numbers (not n numbers).
One Query. Please Clarify @TECH DOSE for example, prices = [1,2,3,4] If we partition in price=2, ([1,2] [2,4]) OR ([1,2] [3,4]) ...which one is correct? My question is, in the same day can we sell the stock first and buy the stock ? (i.e. [[1,2] [2,4]] / [[1,3][3,4]] / ...... ) Or, Sell and buy must be in diff day ?
Don't feel bad ... I tried a bottom-up DP approach to this, allocating a jagged array which is essentially O((N^2)/2) space (each cell storing an int), where each row corresponds to the end of the subarray and the column corresponds to the beginning of the subarray, and I also approach this using a divide and conquer (i.e. partition the array in 2 pieces (for the 2 transactions), and calculate max profit per subarray (calculating just once), and I don't get any TLE, but I blow up memory about test case 202 (of 214). I'm now trying to figure out how I can calculate better the next partition based on the previous partition. It's vicious (that's why it's hard).
that divide and conquer approach simultaneously gave me Goosebumps but also left me in awe by the pure beauty of the approach..... As always really appreciate your work.....thank you.!!!
Maybe divide and conquer don't strike but recursion should be intuitive if you had solved cooldown problem or if you have practiced enough on backtracking. So try to think about observations and try to see if a problem can be framed or converted to other problem. This was you can practice to improve yourself.
I think, number of calls in that case will also be 2^n, only difference is it will not calculate all the cases as the repeated ones are already stored. Please correct if this is wrong.
Isn't this divide and conquer approach O(n^2)? As you have to loop over each element, and for each element check all elements to its left and right? In fact, my implementation of this method exceeds time limit on leetcode...
I have doubt, how do we come up with divide and conquer approach. i mean, How do we come to know that create left and right array with values and summing up them will give us the result.Is there any logical sequence behind this summing technique, from left to right i understood, but from right to left i am unable to get on what ground we are confirmed that taking max will work. I am confused in that, Will be huge help if you can clear this doubt please. I have solved it with recursion, but that wasnt accepting on IB, so i came across your d&c approach, please clear this doubt, thanks and really appreciate your work..
@@techdose4u Yes seen that, but it's not mentioned in the given problem description. Apparently ,we have to assume that. Well thanks for the reply. Cheers!
Maybe they want divide and conquer. Interviewbit may set their requirement for the most optimal. Try the same on leetcode with DP. It depends of what complexity they are expecting.
@techdose Why are we going from end to middle in case of the right side from center and why not go just like he left side which is (along the timeline and not against)
sir one request from deepest of my heart ,and soul . can u make its 4th part, which i consider the toughest among all. plz sir , plz i beg u.plz make it , placement session is going on.
@@techdose4u and sir in ur telegram channel u said to ask questions there, but how can we message in a channel, telegram doesn't allow that, plz create a group sir, thank you very much sir
Sir I am solving leetcode challenges since from 1 and half month , but some of problem I can't able to solve by my own ,once I watch solution then I think that I don't know even simple logic also, then i feel sad, then i close the laptop, sir can you give me any suggestions I want to become like u sir,
Just spend some time about thinking the problem. Try harder each time. If you can't solve then read editorials and try to code yourself. You will definitely improve :)
Thank you very much for such a wonderful explanation.Intuition development is very Important rather than coding and learning formula for this problem and you have explained it in depth with appropriate examples. Please keep making videos like these.
Thanks
I really like that you explained the thought process behind implementing memoization. Thank you for that!
Welcome 😊
Awesome video! In principle, we don't need the 1st loop, and going further we can solve even in one scan.
👍🏼
Subscribed right away. Cant imagine the amount of work this creator is putting in making these videos. Hats Off.
Thanks
Why UA-cam doesn't have option for liking more than once?
Great explanation man🔥
Thanks : )
i should take max(profit, left[i]+right[i]) . if we take left[i-1] we're excluding a fact that ith element may be the maximum of left subarray and minimum of right subarray.... in that case. transaction where we sell on ith day while we bought from a day on left, is ignored. and if we have to sell and buy on same day... that's same as holding it, because left subarray ensures that we've already purchased before we're trying to sell. check for the input.. 1 2 3 4 5 . now consider 3 as pivot.. profit left = 1, and profit right = 5-3 = 2.. total profit = 3... but max profit is 4. 5-1.
This needs to be pinned. I was facing the same issue and resolved this by myself but was looking for the explanation. Thanks :)
I think its somewhat complicated to explain but you explained well !
here is a easy approach :
class Solution {
public int maxProfit(int[] p) {
int pr1=0;
int pr2=0;
int mn1=Integer.MAX_VALUE;
int mn2=Integer.MAX_VALUE;
for(int i=0;i
Best explanation series on Buy And Sell Problems !!
Thanks :)
I don't think this could have been explained better than you did
Thanks buddy :)
I think the string operation glossed over in the middle is actually O(1) (since the length of the string would be constant) as it's just concatenating 3 numbers (not n numbers).
Explained very well and smoothly converted complex problem into simpler one. Thanks for such wonderful video.
wow..that divide and conquour approach is super
amazing devide and conqure approach
Thanks 😄
For any newcomers, the divide and conquer approach is the easiest to understand.
Amazing explanation. Hats off to you for putting so much efforts.
Thanks :)
Was struggling with this question and the intuition behind the soln for the whole day. As always TECH DOSE saves the day.
Very well explained. Hats off to Tech Dose!
Thanks :)
thanks a lot, dude, ur detailed explanation definitely helped understand the crux of the problem.
keep up the great work.
Thanks
Great Explanation! Really helpful to understand.
Nice :)
Kicking off the day with this video 🔥
Nice :)
Best Explanation for this problem.
Thanks :)
Great Explanation!!!
Thanks
Wonderful!! Finally a very good explanation!! Thanks a lot.
Divide and conquer easy damn easy thanks a lot
Great explanation. Keep up the good work
Thanks :)
One Query. Please Clarify @TECH DOSE
for example, prices = [1,2,3,4]
If we partition in price=2, ([1,2] [2,4]) OR ([1,2] [3,4]) ...which one is correct?
My question is, in the same day can we sell the stock first and buy the stock ? (i.e. [[1,2] [2,4]] / [[1,3][3,4]] / ...... )
Or, Sell and buy must be in diff day ?
Beautiful explanation
This is some next level stuff thank you so much sir. you are the real deal.
Please explain how to choose the dividing line in the divide and conquer approach
I did it in O(n) time and space still 5%,5% on leetcode!!!!!!!!!!!!!!
Don't feel bad ... I tried a bottom-up DP approach to this, allocating a jagged array which is essentially O((N^2)/2) space (each cell storing an int), where each row corresponds to the end of the subarray and the column corresponds to the beginning of the subarray, and I also approach this using a divide and conquer (i.e. partition the array in 2 pieces (for the 2 transactions), and calculate max profit per subarray (calculating just once), and I don't get any TLE, but I blow up memory about test case 202 (of 214). I'm now trying to figure out how I can calculate better the next partition based on the previous partition. It's vicious (that's why it's hard).
what is the time complexity of recursive solution after memoization ??
Big cheers to you man, explained really well!!!!🙌
Amazing explanation brother...Thank you so much
Shortest Code Ever:-
int maxProfit(vector& prices) {
int n=prices.size();
if(n==0)
return 0;
int k1=0,k2=0,b1=-prices[0],b2=-prices[0],K1,K2,B1,B2;
for(int i=1;i
watching his amazing explanation at 3:20 am while waiting for 4:20am
Wow 😅
The idea(Divide and conquer one) is kind of related to the candy peoblem in leetcode.
👍🏼
@@techdose4u Hey how about when we generalize and say k transactions are allowed then we will have to apply the memoization approach?
amazing explanation, thank you very much sir!
Wow !!! This is really an awesome explanation.
Thanks
You are awesome. Very nice explanation.
Thanks
You should upload on Box stacking DP problem. No good content is available on this topic. Thanks in advance!! ❤️
Okay I will try
@@techdose4u thanks!❤️ Can you do it sooner?😅 Interview date is near.
You are the Best .
Simply , Loved it !
Nice sir but in real practice we can sell a stock before buying .Thank you for amazing explanation
Just tell me how will it come to my mind?
How can one think this optimal approach by own?
that divide and conquer approach simultaneously gave me Goosebumps but also left me in awe by the pure beauty of the approach..... As always really appreciate your work.....thank you.!!!
Nice explanation! Thanks!
Welcome :)
Amazing explanation....so easy to understand.
Thanks :)
thank you man , this was amazing
Welcome :)
why is time complexity 2^n for memoization?
Nice intuitive explanation!
Thanks
sir, nice explanation, but how to get idea , the idea is not striking at all, when i see a new kind of problem, please help
Maybe divide and conquer don't strike but recursion should be intuitive if you had solved cooldown problem or if you have practiced enough on backtracking. So try to think about observations and try to see if a problem can be framed or converted to other problem. This was you can practice to improve yourself.
very good explanation sir
Thanks
Amazing!!!! Could you explain the time complexity after adding memoization to the recursive solution? You didn't mention that
I think, number of calls in that case will also be 2^n, only difference is it will not calculate all the cases as the repeated ones are already stored. Please correct if this is wrong.
Good Explanation
Great Explanation
Thanks
Very useful! Thank you
Welcome :)
Wow you just never stop surprising me. I am speechless!! Can I be your student please ？！！！😉😉
You are not just a student 🤪
Isn't this divide and conquer approach O(n^2)? As you have to loop over each element, and for each element check all elements to its left and right? In fact, my implementation of this method exceeds time limit on leetcode...
Can you please suggest some more problems to practice peak valley approach.
Other versions of this problem are on similar logic. I had covered more of such videos in challenges but don't remember the name 😅
Fantastic!
Great stuff again ☺️.. Thank your
Welcome :)
If you don't come up with the solution , ask the interviewer to explain it to you
😂
I have doubt, how do we come up with divide and conquer approach. i mean, How do we come to know that create left and right array with values and summing up them will give us the result.Is there any logical sequence behind this summing technique, from left to right i understood, but from right to left i am unable to get on what ground we are confirmed that taking max will work. I am confused in that, Will be huge help if you can clear this doubt please. I have solved it with recursion, but that wasnt accepting on IB, so i came across your d&c approach, please clear this doubt, thanks and really appreciate your work..
Sir can we solve this problem using state machine?
Can't we sell and then buy that same stock on the same day? Or, are we already taking that into account here in the mentioned process. Please explain.
We can't sell before buying and we cannot perform multiple operations on the same day. Only buy or sell on a day. I had said about this in the video.
@@techdose4u Yes seen that, but it's not mentioned in the given problem description. Apparently ,we have to assume that.
Well thanks for the reply. Cheers!
Yea it was not clear.
Thank you !!
Welcome :)
Awesome
Thanks
in memoization case time complexity would be O(2*3*n) => O(n) right?
I don't know
your dp approach is not getting accepted on interviewbit.
Maybe they want divide and conquer. Interviewbit may set their requirement for the most optimal. Try the same on leetcode with DP. It depends of what complexity they are expecting.
@@techdose4u ya It is fine for leetcode
Sir really very amazing 😍😊 video and explanation is seriously beautiful and 😍😍😍
Thanks :)
thx for ur video!
Nice explanation. Can you please make video for Best Time to Buy and Sell Stock with transaction fee
i dont understand why u are moving in opposite direction we can also move from the i th position towards nth position
After buying a stock fall in - 5% what is the calculatin of profit and loss kingly guide me
This is gold!!
😁
Can you please tell the time complexity of the memoized solution for this problem !!
what will the overall time complexity of memoization approach ??? please do reply
is any iterative solution possible
thank you sir.
Why do we need 3 states? At end of the day, there're only 2 states anyway, either hold cash or hold stock.
Amazing
could someone explain difference between buy and sell stock2 problem and buy and sell stock 3 problem
It's almost like you've hacked the human brain. *_*
Cant believe I understood it in a single go!
@techdose Why are we going from end to middle in case of the right side from center and why not go just like he left side which is (along the timeline and not against)
Please add timestamps for long videos
Sure
can you please tell how time complexity of state machine code will be O(n)
how did you know all this, sir?
is there a book that teaches you how to tackle these problems ?
There is no such book 😅
@@techdose4u but sir, this is very unintuitive for me, how do i learn about all this?, this is the first time i see dp problem with more than 1 state
sir one request from deepest of my heart ,and soul . can u make its 4th part, which i consider the toughest among all. plz sir , plz i beg u.plz make it , placement session is going on.
Okay I will make it.
@@techdose4u and sir in ur telegram channel u said to ask questions there, but how can we message in a channel, telegram doesn't allow that, plz create a group sir, thank you very much sir
I have created both group and channel. Join both. They have different uses.
@@techdose4u oops i only saw the channel link, now i got it.
Sir I am solving leetcode challenges since from 1 and half month , but some of problem I can't able to solve by my own ,once I watch solution then I think that I don't know even simple logic also, then i feel sad, then i close the laptop,
sir can you give me any suggestions
I want to become like u sir,
Just spend some time about thinking the problem. Try harder each time. If you can't solve then read editorials and try to code yourself. You will definitely improve :)
@@techdose4u yeah I will definitely do sir,thank you sir
why going backwards works?
Ok, so i understand it. (* starts crying in background).
??
@@techdose4u why going backwards (i.e. selling first and buying later) or reversing timeline for 2nd array works?
divide and conquer @ 14:16
how can i see the implemented class behind the function on leetcode . please help me
I don't think you can.
@@techdose4u but i did many times now i forgot how i did that or may they removed that option
@@techdose4u you are doing good may i suggest you something which i feel you should work on that related to presentation
@@utkarshpanwar2358 check successfully submitted solution, there are bars....for all usecases... click b on bar ... it will show underline program
𝙄 𝙖𝙢 𝙖𝙙𝙙𝙞𝙘𝙩𝙚𝙙 𝙩𝙤 𝙙𝙤𝙨𝙚𝙨 𝙜𝙞𝙫𝙚𝙣 𝙗𝙮 𝙏𝙀𝘾𝙃 𝘿𝙊𝙎𝙀.🔥🔥🔥🔥
Great :)
Thanks :)
which software do you use sir? is it openboard
Wacom pro sketch.io
Would you please add subtitle in your video?
I am trying. I hope it's fixed soon. I am getting some problem in auto-generated English sub.
Can anyone tell that in the preferred language if I have wriitten java in kick start competition then I will get only java to use in coding??
Legends come at night 😁😁
😂
Why t=0 is out of bound.
T
GOD
😅