d[i][j] means: 1) if range [i to j] is to be burst AND all other range [0 to i] and [j to len] are STILL THERE. 2) dp[i][j] is the max value to get for condition 1) 3) to calculate d[i][j], we examine all k (i
Literally the first point here made me understand the whole video. I was struggling to understand any of the other comments trying to explain the video. Thanks a lot.
notes：1) I think this reduce to matrix multiplication chain problem. 2) the 2-d Grid represents a range of subarray i to j. 3) Cell in grid notes down the local max value result and the index of last balloon to collect the burst order at the end. 4) The last ballon to burst in range i to j means if we burst this last ballon all i to j r gone and the rest of balloons r untouched.5) code implementation for loop len->start index of subarray->last balloon to burst
I'm not sure if he mentioned this in the video, but the algorithm he is using is not just a dynamic programming algorithm. It's also a divide and conquer algorithm, it's just done bottom up. First solve the problem using a recursive divide and conquer algorithm, then you can add memoization or convert it to a bottom up algorithm like his. It would still be tough to get this running perfect in an interview.
isko nhi aata hai bro. lets just appreciate what he is doing. because many times you won't get any other soln than his. getting something is better than nothing
@@VikramKumar-wd4dr "isko nai aata hai bro" hahaha...considering that he has worked for top companies like Apple before, I think he probably has good problem solving skills...so he might be able to explain the thought process as well.
He explained the idea. The idea is to break the problem down to simpler problems and use those sub problems to solve the bigger problem. So find the maximum value of all the subarrays and then we can find our answer from building off that. Start with the smallest subarray length possible (1) and do all of those subarrays then build up to length 2, 3, ... n. For example if we are trying [3,4,1,2] then start with subarray [3] and calculate by taking the max results of previously calculated values to the right and previously calculated values to the left (both are 0 in this case since we have length of 1) plus 1 X 3 X 2 = 6 (the values to multiply from left right and current value). So the idea is at each position we calculate our value by multiplying it with the right and left with ourself then we add the previously calculated results that did the same process. Repeat this process for all the other subproblems and build up from there. Once we fill out all the subproblems we will have our answer. It's an optimization problem so we have to try all possibilities and using dynamic programming we can cache or memoize the intermediate results for later re-use to solve the larger problem. Another solution would be to use recursion with memoization which has the same idea of breaking the problem down to smaller sub problems. You get to the idea by noticing the recursive nature of the problem.
Hard problems can be so frustrating! I had a similar idea as Tushar (not perfect, hence why I'm watching this), but I arrived at the idea by reading the entire chapter of Dynamic Programming in the CLRS book.
Tushar Roy Great video! **But I think there is a mistake on **15:32** ** If 2 is the last balloon to burst with length 3, you should check on the table [1,1] = 15, but you considered 3. For that you should have: 15+40+ (3*5*1) = 70 instead of 58. Please, check that and tell me if I'm mistaken.
A minor observation, you can take out the code for leftvalue and rightvalue out of the innermost 'for' loop as it's value is independent of 'k'. It saved some processing in my brain. Great video!
Awesome videos. One request, before starting the solution if you could direct watchers to pause the video and try it themselves by giving a hint or so, that would be very encouraging.
Tushar , your content is very useful to us . Although you don't explain how you reach there but I think that's understandable keeping in mind the list of companies you have worked at already( maybe these come naturally to you.)
I think it is beacuse while solving for let's say length 3, we first require max result of length 2 and then we burst the third balloon, i.e. result of length 2 was calculated while all the balloons were not burst and hence will influence the result of length 2. Influence of outer elements on result of subarray is the reason this question is solved using Dynamic Programming and not divide and concur. hope this helps.
can you please explain . when you said consider a subset which starts at one and ends at one. for e-g . 1 3 5 8 you said if subset of length 1 that starts at 0 and ends at 0 then answer you get is -> 0 + 0 + 1*1*3 =3 how can you add 1*1*3 , when 1 is the only element in the subset and is last element to burst.?
Do not get confined within that subarray. It's a typical bottom up DP approach. Perhaps his explanation was a bit ambiguous but it makes sense once you think if that was the last balloon to burst how much value would you get ? The answer is : nums[-1] * nums[i] * nums[n].
i think length = 1 means.. in this array {3, 1, 5, 8}, what is the max number if only 1 burst. and so forth. So he can still takes the adjacent balloons as they are still there.
Add value only when there is a burst. Otherwise, the value is 0 (no balloons are burst). For example, say, subarray of size=3 is for index [0 1 2], we are bursting three balloons. If we burst balloon 0 last, we are not bursting any balloon on the left of balloon 0. So, we get value of 0 from left. We are bursting two balloons from right of balloon 0. We are bursting [1 2] from right in this case. The value for bursting [1 2] calculated is 135. So, for three balloon bursts from subarray [0 1 2], If we burst balloon 0 last, we get value = 0 (no burst on left) + 135 (two bursts on right) + 1 * 3 * 8 If we burst balloon 1 last, we are bursting one from left and one from right before bursting balloon 1. So, the value we get: 3 (one burst on left) + 40 (one burst on right) + 1 * 1 * 8 If we burst balloon 2 last, we are bursting two balloons on left (ie, [0 1]) and not bursting any balloons on right. So, the value we get: 30 (two bursts on left) + 0 (no burst on right) + 1 * 5 * 8
I think there's an error. At 15:32 for length 3, index 2, (1,1) should be 15, right? Thank you for making this video. EDIT: oh, that has already been answered.
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
Last Baloon to Burst- Suppose you have balloons at index 0 1 2 3 4 and you are considering balloons 1 2 3. When It say 2 is last balloon to burst in 1,2,3 I multiply 2 with 0 and 4 which are balloons outside range 1,2,3. If 2 was first balloon to burst then it would have multiplied 2 with 1 and 3.
I don't understand what you mean by last balloon to burst. When you are considering arrays of length = 1, you say it is the last balloon to burst.. for example, in your ex 3,1,5,8.. when we are considering 3, if three is the last balloon to burst, it means that 1,5,8 have all burst already .. i.e., 3 is the only balloon.. so the value should be 1*3*1. Similarly, when 1 is the last balloon to burst, we are considering just one balloon array, so even 1 does not have anything on the left and right, which means the value should be 1*5*1 .. how are you taking it as 3*1*5 ? Please clarify.... Otherwise, great efforts in making the videos and totally appreciate your work
dp[i][j] means bursting all the balloons between [i,j] in the original array. So dp[1][1] means burst only the second ballon in the array, that is why it is 3 * 1 * 5 = 15.
No doubt, outstanding video. :) Wondering if you could cover up the brain storming process (behind the scenes for the future problems). I believe it would be helpful to see and learn 'how you derived the algorithm for any new problem statement'.
Can we do it using heaps as well? Maintain left and right pointers for each balloon. Put all the elements except the first and last in a min heap . Then pop the elements and add the sum obtained upon each popping off of the element. Also simultaneously update the left and right indices for the right and left balloons of the current popped balloon respectively. If there are more than 2 balloons with the same value then select the one which has a larger valued neighbour. At the end just remove the smaller of the 2 corner elements and then the larger corner element.
Hi tushar your videos are so much helpful . could you please make a video for best time to buy and sell with cool down from leetcode . i have gone through your video for k transaction but still not quite intuitive to do cool down one . Would really appreciate your help . Thanks for the great work.
How to proceed if total value will be the sum of ballon[left] * ballon[right].If there is no balloon in left then 1*ballon[right].If there is no balloon in right then 1*ballon[left].If there is no balloon in either side then value at the position itself. Please help me to proceed with this. Thanks.
So, in the 2 examples where the dp tables are constructed, all the indices at each cell(i,i) is either i or j. So, it is easy to backtrack the order of the balloons that are burst. For example in both the cases cell(0,3) is 3. so we can consider 3rd index balloon burst first and we move to cell(0,2) but how to backtrack if cell(0,3) has 2 as an index. This happens in your example of (1,3,5,8) where 5,1,3,8 is the order of bursting. So, in this case how to backtrack? if 2 is the index then split is from (0,1) and (3,3). In this case, how to find the next order?? So, I think, for this solution, we cannot backtrack to find the order of the balloons or we have to always consider the end indices bursting at the last in order to find the order of the bursting balloons!! Anyone please feel free to correct me if I am missing anything.
Thanks and I really love your video! I have one question at 15:54, isn't the 1to1 value is 15 in the table? So it should be 2 -> 15 + 40 + 3x5x1 = 70? (Never mind, I just realized there have been some discussions regarding this.
The intuition behind how this problem gets broken down into sub-problems is beyond me. It's easy enough to translate the balloon value into a function ( v(i) = v(i-1) + v(i) + v(i+1) ) and consider all n! permutations; but, somehow you saw that only continuous sub-arrays need to be taken into consideration. The motivation there is more important than the algorithm details in my opinion.
I agree with you, he didn't explain how to arrive at his solution. I'm not sure if he mentioned this in the video, but the algorithm he is using is not just a dynamic programming algorithm. It's also a divide and conquer algorithm, it's just done bottom up. First solve the problem using a recursive divide and conquer algorithm, then you can add memoization or convert it to a bottom up algorithm like his.
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
Hello Tushar. I am a regular follower of your videos and you are simply fab. I have a request. If possible, please make a video tutorial on DP with bit masking as I am struggling a lot to understand the topic (taking in consideration spoj problem ASSIGN). Thanks in advance.
today in our campus placements at MNNIT Allahabad Samsung asked this problem. time given was 3 hrs still couldn't complete.hope had watched it earlier.... :(
Future notes for myself:- hey it's just a simple MATRIX CHAIN MULTIPLICATION. But we need to add 1 and 1 at the begin and end because unlike matrix chain multiplication, we can have our first balloon or the last balloon popped and if that happens i-1 or i+1 will be absurd and that's why we add 1 and 1 in the start and end to balance this situation.
I am still unable to visualize the formula you used in. I got the formula and understand the solution. I am still wondering how you derived the formula. Which one to add and which one to consider and which one not to consider.
He is essentially doing a divide and conquer algorithm from the bottom up. The divide and conquer algorithm for this problem is a recursive function that for every element in the array, calls itself for the items on the left and the items on the right. Once you realize this works. Then convert it to a bottom up solution and you will end up with something very similar to him
I still confused about the beginning. U said think about len = 1, and it is the last ballon to burst. Let's the second element 2. left side and right side are both nothing. so why the value is not 1 * 1 * 1, but it's 1*3*5? You said that's the last ballon u need to burst right?
Initially I also thought the same but one thing you need to understand that here when we are selecting only a subproblem for say i to j the problem has to be dealt in context to the entire array, its not complete independent and the order of elements in the entire array effects all the subproblems. so when selecting subproblem i to j we are just bursting those balloons but have to consider rest of the balloons for the last one.
Hi, I noticed you had code for this problem in your github: www.geeksforgeeks.org/reorder-a-array-according-to-given-indexes/ However, I don't exactly understand why the algorithm works. Could you perhaps make a video for this problem, please?
Here is the problem. essentially: Given two integer arrays of same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to given index array. It is not allowed to given array arr’s length. Example: Input: arr[] = [10, 11, 12]; index[] = [1, 0, 2]; Output: arr[] = [11, 10, 12] index[] = [0, 1, 2] Input: arr[] = [50, 40, 70, 60, 90] index[] = [3, 0, 4, 1, 2] Output: arr[] = [40, 60, 90, 50, 70] index[] = [0, 1, 2, 3, 4]
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
Based on my understanding, the explanation at some point is not right! I think it should be "FIRST balloons to burst" and incorrectly he said "LAST balloon to burst". It means, at the first round, as brought in diagonal squares in the DP's matrix, we assume that if a balloon is the first balloon to burst what will be the value. By the way, the explanation for the top right of the matrix (which consider as the last balloon to burst" is right.
Since at the first round (sub-array with length 1), we only have one balloon, FIRST and LAST balloon are refer to the same element and from that point maybe you right. But your algorithm consider that as the FIRST balloon to burst (and because of this you multiply that balloon with its two adjacent). So, based on this logic it's better to mentioned that as FIRST balloon to burst to prevent misunderstanding for others. By the way, thank you for your effort and nice explanation.
Let me clarify it. Suppose you have balloons at index 0 1 2 3 4 and you are considering balloons 1 2 3 When I say 2 is last balloon to burst in 1,2,3 I multiply 2 with 0 and 4 which are balloons outside range 1,2,3. If 2 was first balloon to burst then I would have multiplied 2 with 1 and 3.
This one is correct. What I mean was at the first round, when you consider sub-array with length 1. In that case, your algorithm consider balloon to burst as FIRST. But your explanation mentioned it as LAST, and this part make ambiguous the process for audience. To clarify, consider index 1 (value 1) in your video (at 5:15). When you wanna calculate it, you said 3*1*5. It means you consider this balloon as the FIRST one and because of this you multiply 1 with 3 and 5 (the left and right adjacent).
dp[1][1] means only burst 1 ballon and that is the ballon in index 1. That is why you confused this part because when you only burst one balloon the fist one is also the last one........
@@evantheking I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
can you please explain . when you said consider a subset which starts at one and ends at one. for e-g . 1 3 5 8 you said if subset of length 1 that starts at 1 and ends at 1 then answer you get is -> 0 + 0 + 3*1*5=15 how can you add 3*1*5 , when 1 is the only element in the subset and is last element to burst.?
I had same issue, will try to clear it. it's not last element of array, its just the last element of this subset 1 {3} 5 8. so other array elements are there. => 0 + 0 + 3*1*5=15 => total coins 3 earns from left of this subset + total coins 3 earns from right of this subset + to coins it earns from its surroundings.
d[i][j] means:
1) if range [i to j] is to be burst AND all other range [0 to i] and [j to len] are STILL THERE.
2) dp[i][j] is the max value to get for condition 1)
3) to calculate d[i][j], we examine all k (i
Literally the first point here made me understand the whole video. I was struggling to understand any of the other comments trying to explain the video. Thanks a lot.
This really helped me understand the solution. Thanks.
thank you! Your comment helps me understand the video
very elegant
notes：1) I think this reduce to matrix multiplication chain problem. 2) the 2-d Grid represents a range of subarray i to j. 3) Cell in grid notes down the local max value result and the index of last balloon to collect the burst order at the end. 4) The last ballon to burst in range i to j means if we burst this last ballon all i to j r gone and the rest of balloons r untouched.5) code implementation for loop len->start index of subarray->last balloon to burst
hey you explained really well!!
If took me a while to even understand, don't know how to think of this during an interview...
I'm not sure if he mentioned this in the video, but the algorithm he is using is not just a dynamic programming algorithm. It's also a divide and conquer algorithm, it's just done bottom up. First solve the problem using a recursive divide and conquer algorithm, then you can add memoization or convert it to a bottom up algorithm like his. It would still be tough to get this running perfect in an interview.
@@FelipePrietoHome This algorithm is a variation of Matrix Chain Multiplication. If you know that then this will be easy to a bit.
@@rahulchudasama9363 writing the bottom up is very difficult to understand really it is amusing how this guy is teaching very easily.
Just telling the idea and NOT telling HOW we actually get to the idea to solve a problem is not really useful...
isko nhi aata hai bro. lets just appreciate what he is doing. because many times you won't get any other soln than his. getting something is better than nothing
@@VikramKumar-wd4dr "isko nai aata hai bro" hahaha...considering that he has worked for top companies like Apple before, I think he probably has good problem solving skills...so he might be able to explain the thought process as well.
He explained the idea. The idea is to break the problem down to simpler problems and use those sub problems to solve the bigger problem. So find the maximum value of all the subarrays and then we can find our answer from building off that. Start with the smallest subarray length possible (1) and do all of those subarrays then build up to length 2, 3, ... n. For example if we are trying [3,4,1,2] then start with subarray [3] and calculate by taking the max results of previously calculated values to the right and previously calculated values to the left (both are 0 in this case since we have length of 1) plus 1 X 3 X 2 = 6 (the values to multiply from left right and current value). So the idea is at each position we calculate our value by multiplying it with the right and left with ourself then we add the previously calculated results that did the same process. Repeat this process for all the other subproblems and build up from there. Once we fill out all the subproblems we will have our answer. It's an optimization problem so we have to try all possibilities and using dynamic programming we can cache or memoize the intermediate results for later re-use to solve the larger problem. Another solution would be to use recursion with memoization which has the same idea of breaking the problem down to smaller sub problems. You get to the idea by noticing the recursive nature of the problem.
Hard problems can be so frustrating! I had a similar idea as Tushar (not perfect, hence why I'm watching this), but I arrived at the idea by reading the entire chapter of Dynamic Programming in the CLRS book.
Tushar Roy Great video!
**But I think there is a mistake on **15:32** **
If 2 is the last balloon to burst with length 3, you should check on the table [1,1] = 15, but you considered 3.
For that you should have: 15+40+ (3*5*1) = 70 instead of 58.
Please, check that and tell me if I'm mistaken.
it was overlooked since there was another value greater than this, yes it should be 70
Yes, you are exactly correct. This was a problem in the video. He should have read 15 instead of 3.
I also think so
Boom 💥 lets use bottom up two-d dynamic programming to solve the problem.
Thanks for putting up recursive solutions for DP problems, that helps to understand the approach taken.
You are one of the best mentors! Please keep up with the same methods. Amazing! Thank you!
A minor observation, you can take out the code for leftvalue and rightvalue out of the innermost 'for' loop as it's value is independent of 'k'. It saved some processing in my brain. Great video!
Good point!
Awesome videos. One request, before starting the solution if you could direct watchers to pause the video and try it themselves by giving a hint or so, that would be very encouraging.
this is my last exam and I'm studying with you. Hope that I pass the exam and finally graduate. Your videos are awesome!
Thanks for the video. Nice walkthrough of the complete problem !!
Tushar , your content is very useful to us . Although you don't explain how you reach there but I think that's understandable keeping in mind the list of companies you have worked at already( maybe these come naturally to you.)
Why do you consider elements out of the subarray when calculating the burst total?
I think it is beacuse while solving for let's say length 3, we first require max result of length 2 and then we burst the third balloon, i.e. result of length 2 was calculated while all the balloons were not burst and hence will influence the result of length 2. Influence of outer elements on result of subarray is the reason this question is solved using Dynamic Programming and not divide and concur. hope this helps.
can you please explain .
when you said consider a subset which starts at one and ends at one.
for e-g .
1 3 5 8
you said if subset of length 1 that starts at 0 and ends at 0
then answer you get is -> 0 + 0 + 1*1*3 =3
how can you add 1*1*3 , when 1 is the only element in the subset and is last element to burst.?
yup, my doubt as well.
Do not get confined within that subarray. It's a typical bottom up DP approach.
Perhaps his explanation was a bit ambiguous but it makes sense once you think if that was the last balloon to burst how much value would you get ? The answer is : nums[-1] * nums[i] * nums[n].
i think length = 1 means.. in this array {3, 1, 5, 8}, what is the max number if only 1 burst. and so forth.
So he can still takes the adjacent balloons as they are still there.
Add value only when there is a burst. Otherwise, the value is 0 (no balloons are burst).
For example, say, subarray of size=3 is for index [0 1 2], we are bursting three balloons.
If we burst balloon 0 last, we are not bursting any balloon on the left of balloon 0. So, we get value of 0 from left.
We are bursting two balloons from right of balloon 0. We are bursting [1 2] from right in this case. The value for bursting [1 2] calculated is 135.
So, for three balloon bursts from subarray [0 1 2],
If we burst balloon 0 last, we get value = 0 (no burst on left) + 135 (two bursts on right) + 1 * 3 * 8
If we burst balloon 1 last, we are bursting one from left and one from right before bursting balloon 1. So, the value we get: 3 (one burst on left) + 40 (one burst on right) + 1 * 1 * 8
If we burst balloon 2 last, we are bursting two balloons on left (ie, [0 1]) and not bursting any balloons on right. So, the value we get: 30 (two bursts on left) + 0 (no burst on right) + 1 * 5 * 8
I think there's an error. At 15:32 for length 3, index 2, (1,1) should be 15, right?
Thank you for making this video.
EDIT: oh, that has already been answered.
wait, where it has been answered?
think so too
best channel for coding!
The way he explains is the best!
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
Awesome video big fan loads of love
Last Baloon to Burst-
Suppose you have balloons at index 0 1 2 3 4 and you are considering balloons 1 2 3. When It say 2 is last balloon to burst in 1,2,3 I multiply 2 with 0 and 4 which are balloons outside range 1,2,3. If 2 was first balloon to burst then it would have multiplied 2 with 1 and 3.
I don't understand what you mean by last balloon to burst. When you are considering arrays of length = 1, you say it is the last balloon to burst.. for example, in your ex 3,1,5,8.. when we are considering 3, if three is the last balloon to burst, it means that 1,5,8 have all burst already .. i.e., 3 is the only balloon.. so the value should be 1*3*1. Similarly, when 1 is the last balloon to burst, we are considering just one balloon array, so even 1 does not have anything on the left and right, which means the value should be 1*5*1 .. how are you taking it as 3*1*5 ? Please clarify.... Otherwise, great efforts in making the videos and totally appreciate your work
dp[i][j] means bursting all the balloons between [i,j] in the original array.
So dp[1][1] means burst only the second ballon in the array, that is why it is 3 * 1 * 5 = 15.
No doubt, outstanding video. :)
Wondering if you could cover up the brain storming process (behind the scenes for the future problems).
I believe it would be helpful to see and learn 'how you derived the algorithm for any new problem statement'.
he just copied the solution from leetcode.
Tushar Roy you rock !!!
Nice Explaination Tushar....
This algorithm is a variation of Matrix Chain Multiplication. If you know that then this will be easy to a bit.
Can we do it using heaps as well?
Maintain left and right pointers for each balloon.
Put all the elements except the first and last in a min heap .
Then pop the elements and add the sum obtained upon each popping off of the element. Also simultaneously update the left and right indices for the right and left balloons of the current popped balloon respectively.
If there are more than 2 balloons with the same value then select the one which has a larger valued neighbour.
At the end just remove the smaller of the 2 corner elements and then the larger corner element.
The best explanation for this question.
Hi tushar your videos are so much helpful . could you please make a video for best time to buy and sell with cool down from leetcode . i have gone through your video for k transaction but still not quite intuitive to do cool down one . Would really appreciate your help . Thanks for the great work.
How to proceed if total value will be the sum of ballon[left] * ballon[right].If there is no balloon in left then 1*ballon[right].If there is no balloon in right then 1*ballon[left].If there is no balloon in either side then value at the position itself.
Please help me to proceed with this.
Thanks.
So, in the 2 examples where the dp tables are constructed, all the indices at each cell(i,i) is either i or j. So, it is easy to backtrack the order of the balloons that are burst. For example in both the cases cell(0,3) is 3. so we can consider 3rd index balloon burst first and we move to cell(0,2) but how to backtrack if cell(0,3) has 2 as an index. This happens in your example of (1,3,5,8) where 5,1,3,8 is the order of bursting. So, in this case how to backtrack? if 2 is the index then split is from (0,1) and (3,3). In this case, how to find the next order?? So, I think, for this solution, we cannot backtrack to find the order of the balloons or we have to always consider the end indices bursting at the last in order to find the order of the bursting balloons!! Anyone please feel free to correct me if I am missing anything.
Thanks and I really love your video! I have one question at 15:54, isn't the 1to1 value is 15 in the table? So it should be 2 -> 15 + 40 + 3x5x1 = 70? (Never mind, I just realized there have been some discussions regarding this.
where?
The intuition behind how this problem gets broken down into sub-problems is beyond me.
It's easy enough to translate the balloon value into a function ( v(i) = v(i-1) + v(i) + v(i+1) ) and consider all n! permutations; but, somehow you saw that only continuous sub-arrays need to be taken into consideration. The motivation there is more important than the algorithm details in my opinion.
I agree with you, he didn't explain how to arrive at his solution. I'm not sure if he mentioned this in the video, but the algorithm he is using is not just a dynamic programming algorithm. It's also a divide and conquer algorithm, it's just done bottom up. First solve the problem using a recursive divide and conquer algorithm, then you can add memoization or convert it to a bottom up algorithm like his.
Thank you Tushar Roy :) you are the best
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
correct its confusing
We don't actually need to store the index. Just storing the value should be sufficient.
Hello Tushar. I am a regular follower of your videos and you are simply fab. I have a request. If possible, please make a video tutorial on DP with bit masking as I am struggling a lot to understand the topic (taking in consideration spoj problem ASSIGN). Thanks in advance.
today in our campus placements at MNNIT Allahabad Samsung asked this problem. time given was 3 hrs still couldn't complete.hope had watched it earlier.... :(
thanks sir.. You also graduated from MNNIT Allahabad only?
which samsung ? location ?
Future notes for myself:- hey it's just a simple MATRIX CHAIN MULTIPLICATION. But we need to add 1 and 1 at the begin and end because unlike matrix chain multiplication, we can have our first balloon or the last balloon popped and if that happens i-1 or i+1 will be absurd and that's why we add 1 and 1 in the start and end to balance this situation.
Really helpful mate
Could you please break down the time complexity a bit more? I can tell it's simple but I'm pretty new to asymptotic analysis. Thank you Tushar!
pls post more , dont stop posting pls
Hi, when you calculate cell(1, 3), if index 2 is the last index to operate, should that be 15+40+15 = 70 instead of 3+40+15?
Alright, thank you.
Very well explained.
Sir you are the best
Hi, Tushar, Can you pls explain "Alien Dictionary Leetcode" on your next video? Thank you so much!
Another best of the best Algorithm video!!!
Can we solve this by using Linked List and backtracking? I think the problem is much clearer to simulate with linked list.
You CAN solve it with backtracking but it will be slow... O(N!).
@tushar if i solve this problem in 0(n^3) if I have to optimize this into o(n^2) or o(n) will it possible ?
Very interesting. What are the applications? I can't find anything refering to this...
Great Explanation.
Thank You :)
did not understand the explanation given by Tushar. Even thought we are considering 1 length ballon but an effect goes to other ballon.
could u plz make a video on this:Generate integer from 1 to 7 with equal probability using rand5()
Is there any way to solve this in less complexity than o(n^2)?
Great video as usual.
btw, can you make a video about Square Root Decomposition?
pls upload some questions on graph
I am still unable to visualize the formula you used in. I got the formula and understand the solution.
I am still wondering how you derived the formula. Which one to add and which one to consider and which one not to consider.
He is essentially doing a divide and conquer algorithm from the bottom up. The divide and conquer algorithm for this problem is a recursive function that for every element in the array, calls itself for the items on the left and the items on the right. Once you realize this works. Then convert it to a bottom up solution and you will end up with something very similar to him
Could not understand at 8:04
please make a video on longest arithmetic progressions.
I still confused about the beginning. U said think about len = 1, and it is the last ballon to burst. Let's the second element 2. left side and right side are both nothing. so why the value is not 1 * 1 * 1, but it's 1*3*5? You said that's the last ballon u need to burst right?
Initially I also thought the same but one thing you need to understand that here when we are selecting only a subproblem for say i to j the problem has to be dealt in context to the entire array, its not complete independent and the order of elements in the entire array effects all the subproblems. so when selecting subproblem i to j we are just bursting those balloons but have to consider rest of the balloons for the last one.
you helped me get over it!
How is he able to store 2 values in the T matrix by just using int? Shouldnt be create a class that contains 2 values???????
Hi @Tushar, great video. Question for you, why do you need to keep track of the last popped balloon in a sub-array while you seem to never use it?
We don't need to keep track of which index gives the best value.
plz do a video on scapegoat trees
Hi, I noticed you had code for this problem in your github: www.geeksforgeeks.org/reorder-a-array-according-to-given-indexes/
However, I don't exactly understand why the algorithm works. Could you perhaps make a video for this problem, please?
Here is the problem.
essentially: Given two integer arrays of same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to given index array. It is not allowed to given array arr’s length.
Example:
Input: arr[] = [10, 11, 12];
index[] = [1, 0, 2];
Output: arr[] = [11, 10, 12]
index[] = [0, 1, 2]
Input: arr[] = [50, 40, 70, 60, 90]
index[] = [3, 0, 4, 1, 2]
Output: arr[] = [40, 60, 90, 50, 70]
index[] = [0, 1, 2, 3, 4]
good
Outstanding !
I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
Aho-Corasick algorithm pleasse
great
Ye kaise kaise questions puch rhe hai interviews me 😥
I know it is Hard , but is it Very Hard?
Based on my understanding, the explanation at some point is not right!
I think it should be "FIRST balloons to burst" and incorrectly he said "LAST balloon to burst". It means, at the first round, as brought in diagonal squares in the DP's matrix, we assume that if a balloon is the first balloon to burst what will be the value.
By the way, the explanation for the top right of the matrix (which consider as the last balloon to burst" is right.
No it is the last balloon to burst.
Since at the first round (sub-array with length 1), we only have one balloon, FIRST and LAST balloon are refer to the same element and from that point maybe you right.
But your algorithm consider that as the FIRST balloon to burst (and because of this you multiply that balloon with its two adjacent). So, based on this logic it's better to mentioned that as FIRST balloon to burst to prevent misunderstanding for others.
By the way, thank you for your effort and nice explanation.
Let me clarify it. Suppose you have balloons at index 0 1 2 3 4 and you are considering balloons 1 2 3
When I say 2 is last balloon to burst in 1,2,3 I multiply 2 with 0 and 4 which are balloons outside range 1,2,3. If 2 was first balloon to burst then I would have multiplied 2 with 1 and 3.
This one is correct. What I mean was at the first round, when you consider sub-array with length 1. In that case, your algorithm consider balloon to burst as FIRST. But your explanation mentioned it as LAST, and this part make ambiguous the process for audience. To clarify, consider index 1 (value 1) in your video (at 5:15). When you wanna calculate it, you said 3*1*5. It means you consider this balloon as the FIRST one and because of this you multiply 1 with 3 and 5 (the left and right adjacent).
dp[1][1] means only burst 1 ballon and that is the ballon in index 1. That is why you confused this part because when you only burst one balloon the fist one is also the last one........
Very Poor Explaination
worst explanation
Can any genius solve this in interview without "seen it before" ?
no . dont beat yourself up . anyone who ask this , they probably dont want to hire you
@@evantheking I can't under anything.If in the first step array size is 1 and last balloon to burst is 5 then we have only one ballon, How can be multiply 5 with left and right balloon then when there are no ballons ?
sorry
can you please explain .
when you said consider a subset which starts at one and ends at one.
for e-g .
1 3 5 8
you said if subset of length 1 that starts at 1 and ends at 1
then answer you get is -> 0 + 0 + 3*1*5=15
how can you add 3*1*5 , when 1 is the only element in the subset and is last element to burst.?
that's exactly I was thinking.
Because profit from subarray [1,1] depends on its neighbours..
I had same issue, will try to clear it. it's not last element of array, its just the last element of this subset 1 {3} 5 8. so other array elements are there.
=> 0 + 0 + 3*1*5=15
=> total coins 3 earns from left of this subset + total coins 3 earns from right of this subset + to coins it earns from its surroundings.