This video has saved me two days of scratching my head while trying to understand the solution in discussion section and still moving on with unclear things in my head The fact that there were no courses like this to learn from during his time and he must have learnt all this with just pure grind and just hours and hours of work blows my mind. He's pouring his years of hard work into these videos and that too for free Thank You Striver !
yah its maxi we need. Just a small mistake guys. it happens at times Anyways the point is we need to go in reverse - last 2ndlast 3rdlast....nthlast(aka first)
one of the toughest problem so far for me, but as soon as you explained the approach of going from last balloon to first balloon, i was able to code it up myself. All this due to your excellent dp series so far!
This is one of your best videos! Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work. Thanks for this video and congrats for making a great one for this problem. ❤❤❤
This is one of your best videos! Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work. Thanks for this video and congrats for making a great one for this problem.
Striver, in the tabulation method, you don't need to check the condition (i > j continue), you can start the jth loop from i, and it will work fully fine. Thanks for making such great videos. This DP playlist is the best gift from your side to the community.
Understood, thanks. Again, this seems to be straight forwardly explained but there's a huge R&D which you might have done to come up with the solution. Thanks a ton for all the help!
aaj tak burst balloons nhi samajh paya tha itne logon ki videos dekhi youTube par but apki video se 1 shot me samajh aagya thanks bhai and understood!!! ofc.
I never learnt dp in scaler like this. I never knew the recursive version in scaler went with tabulation. Striver bhaiya big fan of you I can shout from top of house you made me learn dp like anything. Even during time of scaler i got rejected in first round of amazon. Now I had cleared three rounds maang is a dream for me you will make it come to reality
Understood!! The problem is very similar to MCM question where we assume we are multiplying the selected matrix index at the last and calling 2 recursive functions to solve left and right sub-problems.
Read many solution where they just told that it's MCM add 1s to start and end that's it, but I didn't find it intuitive... This solution is logical rather than mugging up those solution!
Understood bhaiya!! Just a small enhancement, we do not need to check the condition (i>j) , we can start j from i, and the code will work fine. int maxCoins(vector& nums) { nums.insert(nums.begin(),1); nums.push_back(1); int n=nums.size(); vector dp(n,vector (n,0)); for(int i=n-2;i>=1;i--) { for(int j=i;j
THIS PROBLEM IS JUST AN MCM problem. I find this explanation a bit complicated than that approach. You just need to add 1 at the beginning and at the end, then just copy paste the same MCM code with the condition changed from finding min to max and that will work. I think you can see why, if anyone is facing issue let me know here, I'll explain.
if in any interview a guy faces this type of questions for the first and able to come up with a solution at that point because the previous video has helped with the fact that why serial wise approach wouldnot help but thinking of the backward approach is tough
Hi striver. First of all thanks for the explanation. I understood the explanation but when i looked at the code it is exactly similar to other problems we did[say l49 or l50] which were done in a top down approach. So i don't understand how the code is the same for which ever approach we take. If i looked at the code directly without looking at your explanation, i would think we are solving this problem exactly as we did for mcm or break stick problem which should not be the case as the approaches for the problems are totally different. Please help me understand this part. Thank you!
If you dont want to modify the input array. class Solution { public int maxCoins(int[] nums) { return helper(nums, 0, nums.length - 1); } public int helper(int[] nums, int i, int j) { if(i > j) return 0;
Bhaiya in Tabulation in the second nested loop why are we starting from j=1 and not j=i+1??? our j will always be on the right side of i isn't it? (just like in the last examples of partition dp)
i have a thought ... can we place a barrier between any 2 balloons like 1... {1,b1,1,b2,1,b3,1,b4,1,b5,1,b6,1}... so that every subproblem becomes independent? and we can calc the cost by moving 2 steps back and forth instead of 1... correct me if i am wrong...
"Minimum Cost to Merge Stones" Bhaiya please add this problem in your dp series . It's a humble request . I have gone through a lot of solution in leetcode discuss forum but nobody has explained the intuition . This problem was asked in agoda online coding round. It's a pretty important as well as the hardest dp problem i have ever encountered.
Hey!! Striver, I have a question, please. Or anyone who might help. You said we can't burst a balloon from the original array directly because that will make it have dependencies on the next element after b4 bursts. Now, what if, we burst b4, remove it out of the array, then add 1 in its place? Also we will add 1 in the next array's 0th index. Would that work? a = [b1 b2 b3 b4 b5] (b3 BURST )-----------> vector A = 0-> ind-1 A3 BURST A.add(1); A.insert(A.begin(),1); vector B = ind+1 -> n B.add(1); B.insert(B.begin(),1); cost = f(1,A.size()-1) * a[ind] * f(1,B.size()-1); P.S.: I haven't tried this code. It is a question of why won't this work? Please if anyone knows, may you help me out?! AND THANK YOUUU STRIVER FOR THE AMAZING VIDEOSS!!!!!!
THe questions that have to be solved in a particular way are usally solved using partition dp. These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc multiple way to solve and have to find the best way to solve.
@@aryansinha1818 THe questions that have to be solved in a particular way are usally solved using partition dp. These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc multiple way to solve and have to find the best way to solve.
Can anybody tell why we are sorting the array in Min cost to cut stick and not in this? And how to know when should we sort the array and when to not??
class Solution { public: //Very minor changes to 1547. Minimum Cost to Cut a Stick Problem // Which baloon should I burst first? -------> WRONG APPROACH -----> dependant subproblems // Let this baloon be the last baloon to be burst ----> CORRECT int func(int left,int right,vector& cuts,vector& rod,vector& dp) { if(left>right) return 0; if(dp[left][right]!=-1) return dp[left][right]; int ans=INT_MIN; //CHANGE for(int cutatindex=left;cutatindex
Thanks for the good explanation for Memoization. But tabulation explanation was poor. Please explain state in dp. What does dp[i][j] store? We require intuition for tabulation and not shortcuts.
The intuition comes from recursion, whatever i and j were in recursion, its the same in iteration as well, Since you memoize dp[i][j], you must be knowing what it means when you memoizing, its the same in iterative. I am sorry, but people who tend to look for everything fetched on their plate end nowhere. Good luck, apply brains, everything is there in the lecture.
This video has saved me two days of scratching my head while trying to understand the solution in discussion section and still moving on with unclear things in my head
The fact that there were no courses like this to learn from during his time and he must have learnt all this with just pure grind and just hours and hours of work blows my mind.
He's pouring his years of hard work into these videos and that too for free
Thank You Striver !
At 22:36 there is mistake it will be mini = max(mini, cost)
yes upvote every one so that everyone can see this mistake👍
i think striver wanted to use maxi = max(maxi, cost) like he uses always
yah its maxi we need. Just a small mistake guys. it happens at times
Anyways the point is we need to go in reverse - last 2ndlast 3rdlast....nthlast(aka first)
maxi = max(maxi, cost)
Your videos have helped me to get to Google. Thanks a lot for making such helpful stuffs.
Bhaiya can you Kindly say how much does cp profile matter for google at 1-2 years of experience? Thank You very much... 🙏
@@abh9789 I didn't had any. I solved the SDE sheet religiously and followed his videos and some other folks videos (techdose and codebix).
@@gopeshkhandelwal9823 May I ask which college are you from? Did you join google as a fresher? Thank You..
@@abh9789 No, I am not a fresher. I had worked with Amazon for 1.5 years earlier after the college.
You proved that we don't need scaler.
one of the toughest problem so far for me, but as soon as you explained the approach of going from last balloon to first balloon, i was able to code it up myself. All this due to your excellent dp series so far!
Same. The moment he said it, the whole solution struck me. Sadly, I could not come to the conclusion myself.
This is one of your best videos!
Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work.
Thanks for this video and congrats for making a great one for this problem. ❤❤❤
This is one of your best videos!
Burst Balloons has got to be one of the most complex problems for anyone solving it for the first time, and your explanation makes it clear how the methods we would normally begin with won't work, and why starting from the bottom WILL work.
Thanks for this video and congrats for making a great one for this problem.
Striver, in the tabulation method, you don't need to check the condition (i > j continue), you can start the jth loop from i, and it will work fully fine. Thanks for making such great videos. This DP playlist is the best gift from your side to the community.
I have done the same..
Understood, thanks.
Again, this seems to be straight forwardly explained but there's a huge R&D which you might have done to come up with the solution. Thanks a ton for all the help!
Yups, true.
18:46 is the moment i was completely shocked I MEAN damn Man, this is BEST EXPLANATION SO FAR. Respect++
same
Hardest Problem in entire dp series i ever watched . same qn. was asked in Samsung. TY striver :)
There is no way on god's green earth anyone can comeup with this approach under pressure in an interview.
Im a living proof of this😢
Understood. I was a bit confused at first, but then it clicked! Great explanation as always!
FIRST/LASY Guy concept instead of level by level or index by index. Great explanation. Striver is the GOAT of DP.
aaj tak burst balloons nhi samajh paya tha itne logon ki videos dekhi youTube par but apki video se 1 shot me samajh aagya thanks bhai and understood!!! ofc.
Hey Striver, Thanks for the wonderful explanation of the problem.
Can you make more videos on the logic of reverse thinking in DP?
i am now in codenation just because of you striver
UNDERSTOOD.......Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I spent whole day in figuring out the solution myself but I couldn't make it.Thank you for great explanation in simplest way.
I never learnt dp in scaler like this. I never knew the recursive version in scaler went with tabulation. Striver bhaiya big fan of you I can shout from top of house you made me learn dp like anything. Even during time of scaler i got rejected in first round of amazon. Now I had cleared three rounds maang is a dream for me you will make it come to reality
Hi, is scaler worth it or not?
did you get maang? how are you doing nowdays.
This is very imp question, it was asked in an interview of a really big company with extremely high CTC
i fucking love coding because of solutions and explainations like this. god tier work.
Until 12:00 I understood the actual neighbor's part. But after that things were not getting clear. It felt like you skipped something
Hah, had to watch this 4 times to understand the intuition behind the solution. One of the toughest problem I have seen till date
Understood!! The problem is very similar to MCM question where we assume we are multiplying the selected matrix index at the last and calling 2 recursive functions to solve left and right sub-problems.
Didn't understand the if(i>j) continue; statement
In the tabulation approach, in the second for loop, we can run j from i to n.
yes
understood it but this was the tough one. To come up with the right approach for such questions is the most difficult part.
Read many solution where they just told that it's MCM add 1s to start and end that's it, but I didn't find it intuitive...
This solution is logical rather than mugging up those solution!
Really a great, clean, clear and concise solution.
Understood Bro , Thanx for the wonderful explanation 👍
Understood bhaiya!!
Just a small enhancement, we do not need to check the condition (i>j) , we can start j from i, and the code will work fine.
int maxCoins(vector& nums) {
nums.insert(nums.begin(),1);
nums.push_back(1);
int n=nums.size();
vector dp(n,vector (n,0));
for(int i=n-2;i>=1;i--)
{
for(int j=i;j
Wow-what an awesome explanation sir. Thanks for all the hard work that you put in, in making these videos.
Bro ,u can use backtracking like keep bool array for bursted balloons ,and then calculate from top to down itself
Yes, you can, but you cannot apply Memoization to it!
THIS PROBLEM IS JUST AN MCM problem. I find this explanation a bit complicated than that approach.
You just need to add 1 at the beginning and at the end, then just copy paste the same MCM code with the condition changed from finding min to max and that will work.
I think you can see why, if anyone is facing issue let me know here, I'll explain.
how it is working, can you share your code?
best question and explanation in my coding journey
You don't know but you will gave india a top notch quality engineers even the 12th students have started DSA 😅
amazing explanation to an amazing problem, thankyou. Understood!
if in any interview a guy faces this type of questions for the first and able to come up with a solution at that point because the previous video has helped with the fact that why serial wise approach wouldnot help but thinking of the backward approach is tough
Understood! Aaaaaaaamazing as always, thank you very much!!
Thanks was struggling with the problem a lot. But atleast did the tabulation myself.
i did not understand if u are considering it the last one then why didn't you multiply with 1 instead of neighbours????
Hi striver. First of all thanks for the explanation. I understood the explanation but when i looked at the code it is exactly similar to other problems we did[say l49 or l50] which were done in a top down approach. So i don't understand how the code is the same for which ever approach we take. If i looked at the code directly without looking at your explanation, i would think we are solving this problem exactly as we did for mcm or break stick problem which should not be the case as the approaches for the problems are totally different. Please help me understand this part. Thank you!
If you dont want to modify the input array.
class Solution {
public int maxCoins(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int i, int j)
{
if(i > j)
return 0;
int max = Integer.MIN_VALUE;
for(int k = i; k
thanks wt is difference btn last problem & this problem both codes looks same. last one sorted this one no need to sort
kirti purswani wala burst balloon bahut acha hai. wo bhi dekhna kabhi
Thankyou so much for amazing explanation Striver
Thank you so much Striver, Understood.
Understood ❤❤❤❤❤❤
Partition Array for Maximum Sum 1
Palindrome Partitioning II
Scramble String
Burst Balloons 2
Bhaiya in Tabulation in the second nested loop why are we starting from j=1 and not j=i+1??? our j will always be on the right side of i isn't it? (just like in the last examples of partition dp)
Yes, u can, i just wrote a genric way, and then used the if statement inside
THANK YOU SO MUCH STRIVER
i have a thought ... can we place a barrier between any 2 balloons like 1... {1,b1,1,b2,1,b3,1,b4,1,b5,1,b6,1}... so that every subproblem becomes independent? and we can calc the cost by moving 2 steps back and forth instead of 1... correct me if i am wrong...
GOATed explanation!
"Minimum Cost to Merge Stones" Bhaiya please add this problem in your dp series . It's a humble request .
I have gone through a lot of solution in leetcode discuss forum but nobody has explained the intuition . This problem was asked in agoda online coding round. It's a pretty important as well as the hardest dp problem i have ever encountered.
23:24 that's a mistake it should be max
Understood clearly need watch it 2 times
bhai ka ek video smjhne m meri video.length*2 ka time lg rha h.......
Hey!!
Striver, I have a question, please. Or anyone who might help. You said we can't burst a balloon from the original array directly because that will make it have dependencies on the next element after b4 bursts. Now, what if, we burst b4, remove it out of the array, then add 1 in its place? Also we will add 1 in the next array's 0th index. Would that work?
a = [b1 b2 b3 b4 b5] (b3 BURST )-----------> vector A = 0-> ind-1 A3 BURST A.add(1); A.insert(A.begin(),1);
vector B = ind+1 -> n B.add(1); B.insert(B.begin(),1);
cost = f(1,A.size()-1) * a[ind] * f(1,B.size()-1);
P.S.: I haven't tried this code. It is a question of why won't this work? Please if anyone knows, may you help me out?!
AND THANK YOUUU STRIVER FOR THE AMAZING VIDEOSS!!!!!!
US striver , Difficult one to think , If i was asked this , I would ask for a diff problem
i want to ask that in approach raj bhaiya said that we have to move from down to solve it but in solution it moves from top how?
Can you please explain how to know that a question requires a partial DP approach?
Good question. Did you find the answer?
@@aryansinha1818 no
THe questions that have to be solved in a particular way are usally solved using partition dp.
These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc
multiple way to solve and have to find the best way to solve.
@@aryansinha1818 THe questions that have to be solved in a particular way are usally solved using partition dp.
These questions may have different answer depending on the way we solve eg maths equation with bracket and without bracket,MCM etc
multiple way to solve and have to find the best way to solve.
Hi Bro , you are mega star ⭐️ in creating this kind of tech content in YT ,love you lots 🙏
On 14:0 what means by 1,5 is the range??
Amazing explanation striver bhaiya!!! Thank you so much for such a wonderful content
simply the best !
hey striver my recursive code is giving stackoverflow, cant handle it.
Please help
As always "understood" ❤️
better explanation that than neetcode guy
hey striver..!!
can you explain boolean parenthesization probblem
next in line
Can anybody tell why we are sorting the array in Min cost to cut stick and not in this?
And how to know when should we sort the array and when to not??
This is the best explanation out there.
Not understanding dp partition problems.
Thank you Striver!!Understood
Hey I solved it on my own ❤ Thankyou
Understood, sir. Thank you very much.
did it on my own :)) similar approach to dp 50
U must be
i just want to know how exactly can we identify that a question is of partition type or not
Damn this is extremely awesome!!!
Thanks
Striver please...can you explanation of Merging Stones (leetcode hard) problem...I searched many yt channel but still confused...please help
Understood !! that I haven't understood 🙃🙃
😂😂😂
The Python3 versions of the solutions exceed the time limit (TLE) on LeetCode.
In ur insta post u mentioned it will be the biggest DP series, how many videos left
Understood 🎉
Understood :)
Hard question, beautifully explained!!
Aug'3,2023 04:14 pm
Such a unique approach
so great video, thanks
Definitely understood, great explaination
I don't think its very possible to come up with this kind of a solution if one hasn't solved it earlier
Understood BTW its just similar to cut the stick problem😂😂
can anyone explain in tabulation by n + 2 , if index + 1 goes till j then j + 1 is already there
Thank you!
Understood!
Understood🔥
class Solution {
public:
//Very minor changes to 1547. Minimum Cost to Cut a Stick Problem
// Which baloon should I burst first? -------> WRONG APPROACH -----> dependant subproblems
// Let this baloon be the last baloon to be burst ----> CORRECT
int func(int left,int right,vector& cuts,vector& rod,vector& dp)
{
if(left>right) return 0;
if(dp[left][right]!=-1) return dp[left][right];
int ans=INT_MIN; //CHANGE
for(int cutatindex=left;cutatindex
Non intuitive not a single thought came to solve it like this even after knowing that it requires MCM 😭😭 .
had to watch video for solution
Understood, thanks.
problem link is for different problem
Great Explanation Striver
Thanks for the good explanation for Memoization. But tabulation explanation was poor. Please explain state in dp. What does dp[i][j] store? We require intuition for tabulation and not shortcuts.
The intuition comes from recursion, whatever i and j were in recursion, its the same in iteration as well, Since you memoize dp[i][j], you must be knowing what it means when you memoizing, its the same in iterative.
I am sorry, but people who tend to look for everything fetched on their plate end nowhere. Good luck, apply brains, everything is there in the lecture.
@@takeUforward I got it now. Thanks. I too think that I have got a bad habit of looking for everything served on my plate. Starting to correct it.
Mast hai sir aapka explanation, maja aa gya😀
this is the hardest question among all I've encountered.
Amazing explanation !!