Burst Baloons - Dynamic Programming - Leetcode 312 - Python

[@NeetCode]

💡 DP Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@ClaudioCarvalhoo]

Just wanted to say that your videos are the best Leetcode question explanations on KZbin by a long shot in my opinion. Thanks and keep going!

[@NeetCode]

Thanks Umbreon, you were always my favorite Eeveelution!

[@CarlJohnson-iv7sn]

@@NeetCode lol

[@sarthuaksharma]

I was stuck on this problem for hours. Going through the discuss forum but was not able to get the feel on how to approach and I thought let's see if Neetcode has this. Thank you so much man. One suggestion though if you encounter similar problems It will be really helpful if you can put those in the description. Keep up the good work man

[@poptart007-b2r]

The backtracking solution with some kinda cache is easy to code if you know how to code permutations, but omfg i could never have guessed the tricks on this one by myself, and even less in an interview setting, thanks a lot for the explanation! Here is an iterative bottom up solution that worked for me at 66% faster: class Solution: def maxCoins(self, nums: List[int]) -> int: nums = [1]+nums+[1] dp = [[0 for r in range(len(nums))] for l in range(len(nums))] for l in range(len(nums)-2,0,-1): for r in range(1,len(nums)-1): if l

[@tabeebyeamin9986]

Yes, this code passes 69/70 cases and TLEs on the last one. But it seems you can't do better than O(n^3) anyway, so I am going to use this solution if I get it an interview. I spent 45 minutes attempting this myself and the best I could do was the glorious 2^n bruteforce solution lol. I love that you keep it real and mention you have no idea how we would be able to solve it without seeing it

[@vinayak186f3]

Can I have that 2^n solution please .

[@saiachyuth3460]

@@vinayak186f3 It's the same solution without dp

[@MrPanthershah]

Bruteforce isn't 2^n, it's n^n, I think that's what you meant.

[@nlke182]

If you use @cache decorator it can pass.

[@CaradhrasAiguo49]

@@MrPanthershah Brute force would be to generate all permutations, which is N!, which is asymptomatically less than N^N per Stirling's formula

[@jyotioh3723]

I hope no one gets discouraged while trying to get through this one. I'm almost there, lmao.

[@Hiroki-Takahashi]

I was being so discourged while watching this video lol (I mean, NeetCode's explanation was excellent. This problem is just god damn hard)

[@MAhmadian]

Thank you for clever solution awesome explanation. It throws an TLE which can be fixed by handling the special case which all elements in the list are the same number. if len(nums) > 1 and len(set(nums)) == 1: return (nums[0] ** 3) * (len(nums) - 2) + nums[0] ** 2 + nums[0]

[@sergeychepurnov1328]

I think it ugly, but works for Leetcode's last test case that I believe doesn't needed at interview: //one special test case handled manually //check roughly if (nums.length > 10 && nums[0] == nums[1] && nums[1] == nums[2]) { Set set = new HashSet(); for (int num : nums) { set.add(num); } //check exactly if (set.size() == 1) { int num = nums[0]; // 1 100 100 100 ... 100 100 100 1 - calculate all middle values: (num*num*num)*(nums.length - 2) // 1 100 100 1 - calculate 2 last: num*num // 1 100 1 - calculate 1 last: num int max = (num*num*num)*(nums.length - 2) + num*num + num; return max; } }

[@ayeshsalah]

Could please explain why this works ?

[@dollyvishwakarma2]

this did not work for me

[@ahmedrebei8138]

3:58 I think the complexity would be n! (you get one less item on each level of the tree)

[@vijayola7597]

yes

[@sadekjn]

yes, that solution basically generates all the permutations, which is n!

[@wintersol9921]

So glad to find this video. I have been trying to understand how to solve this problem for 2 days. You explained it in 10 minutes. Thank you very much.

[@bmusuko]

if you guys got TLE on the last testcase, try to change dp hashmap into 2d matrix, since array lookup slightly faster than hashmap lookup. And also you can put `@cache` on top of dfs function

[@girrajjangid4681]

Thanks @bram. It worked by changing dict to 2D list

[@forresthu6204]

Thanks

[@omartahboub2900]

Good Point ! If your interviewer was so busy that day and had bunch of deliverable to be completed, and forgot to give you any useful hints and poor candidate who prepped for so many sleepless weeks to eventually be marked with "No Hire" for such problem the candidate would not encounter working at that company. What a sad reality ! I would imagine many candidates would just memorize the solution and go with odds of "Hit or Miss" until the next 6 or 12-month cool-down cycle.

[@VarunMittal-viralmutant]

I have seen architect level ppl stuck on a problem for weeks, and then when they have 'light bulb' moment, they ask the same question in their next interview. Imagine the poor candidate has just 40 minute to crack the question 😢

[@donotreportmebro]

@@VarunMittal-viralmutant that's a bar raiser

[@VarunMittal-viralmutant]

@@donotreportmebro No matter what you call it. It is unfair and unjust to the candidate. While you were stuck for it for weeks and had multiple ppl brainstorming the solution, the poor candidate is all alone, already under pressure and has just 30 minute to come up with the solution.

[@secretdev1559]

Awesome explanation! There are a few more cases that were added to LC which lead to a TLE despite the same num check. If one takes the DFS approach here and instead leverages iteration, the overhead of the stack can be avoided and a TLE can be avoided. Although the algorithm's RT is still O(n^3) with O(n^2) space complexity. I think that the time limit band on the problem needs to be increased.

[@MrKB_SSJ2]

I watch every LeetCode video of yours!

[@chuckchen2851]

Tried the lru_cache and the manual memoization way as done in the video, both TLE on the 69th case, which has 500 elements. Is the bottom-up approach somehow more efficient than the top-down?

[@nathanx.675]

Same...

[@8Trails50]

it is more efficient - less overhead in computation which leads to it barely being accepted.

[@jongxina3595]

I did it bottom up and worked like a charm first try ✨️

[@Simran_048]

best simple explanation, i was not getting idea before watching this

[@ashwinnema06]

Best explanation I ever found on youtube

[@NeetCode]

Glad it was helpful!

[@houmankamali5617]

If it helps, the way that I justified one could intuitively arrive at the trick is to think about how we could arrive at a subproblem in which the order of the elements is the original list is not modified. The initial approach of starting from popping an element and then calculating the result for the subproblems does not work because the order of the elements in the subproblems are different than the original problem, so we can instead think "how would it help me find a solution if I had the cache result for some consecutive number of the elements?"

[@stevenmo1586]

great insight Houman!

[@harimonting01]

But before deciding to look for possible subproblem, how can we intuitively conclude that this is a dp problem?

[@farleylai1102]

Solution to TLE: 1. Iterative 2. Use matrix instead of hash map cache def maxCoins(self, nums: List[int]) -> int: from collections import Counter nums = [1] + nums + [1] dp = [[0] * len(nums) for _ in range(len(nums))] for L in range(len(nums) - 2, 0, -1): for R in range(L, len(nums) - 1): for i in range(L, R+1): coins = nums[L-1] * nums[i] * nums[R+1] coins += dp[L][i-1] + dp[i+1][R] dp[L][R] = max(dp[L][R], coins) return dp[1][len(nums) - 2]

[@ShamsNahid-gc1cx]

Specially, in JS, without 2d matrix cache, it got a TLE. Thanks

[@snowboarder981]

I really appreciate the work you put into these videos. Your videos are easily the best explanations. I love that you draw things out and talk about multiple solutions before moving to the code. You are best my friend!

[@albertjtyeh53]

It's TLE-ing on the 69/70th case now

[@chowtuk]

the most unsatisfying video from neetcode

[@Rohan-hj9gg]

Thanks for this, can we have video for palindrome partitioning (MCM variation)

[@vinayakmikkal]

What if the array is [3, 1, 5, 8, 2] and the order of popping is [1, 8, 3, 2, 5] so at the end the cost that needs to be calculated is 3*5*2 + other_part, I'm not able to see a situation where the multiplication of 3*5*2 taking place. Am I missing anything?

[@helloadventureworld]

thanks for the video on this one it wasn't an easy one to get to be honest and your explanation made it way easier on me ❤❤❤❤

[@sheltonsong6120]

Thanks for the solution!!! You are the best! I copy paste your solution to Leetcode, and the judge result is Time Limit Exceeded. I believe the solution is definitely correct though, have you tried to submit the results? Leetcode sucks!

[@itachid]

I think there's a mistake at 5:58 when Neet tells that for an array of size N there can be at most N^2 subarrays. But aren't there actually (N * (N + 1)) / 2 subarrays for an array of size N?

[@Ren-j7n]

Well, we don't really care about the specific constants and thereby it is O(N^2) subarrays.

[@sapnavats9105]

What is the need to initialize dp[(l,r)] to 0 and then update it as max of 0 and the newly computed value?

[@chessingh]

because dp is a dictionary and it will give key error, if not already there in the dictionary, try it without initialization you will see

[@DavidDLee]

The reason for initializing to 0 in L12 and then taking the max at L16 is because the code iterates over all nums between [l, r] and finds the max at that range. Now, you must find the max in [l, r], otherwise you'd get the wrong answer (*NOT* a key error though), because you'd probably just take the last value in the range that is likely less than max. Initializing to 0 in L12 is just a convenience, so you could use max also on the first iteration. 0 is guaranteed to be less than any of the possible values.

[@hwang1607]

This is a crazy question

[@SreyesSrinivasan]

Fantastic explanation man! Keep up the great work

[@zelfrax]

@5:17 you made a mistake. We have n! possible combinations. Phrasing it in terms of subsequences does not make sense because we are not concerned with subsequences in this problem.

[@moonhan2157]

You are not correct. Subsequences are important in the subproblem and its 2^n subsequences.

[@VishalKumar-kr9me]

What made you to not check l == r instead go with l > r as the base condition? Could you please explain

[@akhma102]

Thanks, Neet!

[@CaptainDeadpool53]

Is there a way to solve this without using memoization, like the regular DP?

[@ammarqureshi2155]

great explanation, keep it up mate :)

[@sauravgupta7415]

Your voice is sounds like "Hello everyone, this is your daily dose of internet"

[@chenzhuo9]

I got TLE with the same code rip

[@veeresh4441]

fck, there is no way I could think this in an interview

[@NeetCode]

me neither probably, im sure 90% of interviewers would give you a hint tho.

[@BeheadedKamikaze]

@@NeetCode Would you mind explaining how you did arrive at this solution? It's not exactly intuitive. Edit: in case it wasn't clear, I do understand why it works. Just wondering by what process you managed to think of doing this.

[@张灏琼]

why the range is r+1 in L13???

[@ameynaik2743]

Is there a list of problems on leetcode which fall under this category?

[@DarkOceanShark]

Where you able to find?

[@mohakparekh8671]

Excellent explanation! There is one part which I am not able to comprehend. Why can't we use the caching with subsequence? There are 2^n subsequences, but won't the caching of that subproblems help us?

[@mohakparekh8671]

@@numbtubeyou Understood, thanks

[@MuratJumashev]

A possible follow-up question: give me the list of balloons you popped to get these coins 😅 Haven't solved this follow-up myself yet. Whenever I get to the solution, I think I'll have a better understanding of this problem 💪

[@milseq]

This is one of those problems where I'm just going to hope I don't get it.

[@samarthtandale9121]

I think the time complexity of brute force will be n! Right?

[@akshay-kumar-007]

This looks like a variation of MCM. Is my intuition correct?

[@nathanx.675]

This is brilliant!

[@АфанасийШереметьев-б5ч]

A moment of silence for those who got this question in an interview (bonus points for it being the first)

[@keshavmn7283]

I recently got this as the first question in the second round 😢

[@dataman4503]

I would assume that the interviewer wanted to fail you if they ask you this question in interview.

[@NeetCode]

lol me too

[@sagarpotnis1215]

there should be a counter for the time neetcode said "pop" in this video 😂

[@linli7049]

Awesome solution!

[@tomtran6936]

Wow. Really awesome trick and thought process. Nice explanation. Appreciated!. If you don't mind to share how much time you took to figure out of this solution?

[@kalpanagupta6166]

I didn't get why did you compute max operation?

[@GetToKnowShaggy]

I think its time to solve this question again with a iterative approach

[@mahedihassanrabby9553]

Best of the best❤

[@jonaskhanwald566]

MAXIMUM PROFIT IN JOB SCHEDULING?

[@chenzhuo9]

dito

[@nardindev]

i did it in js like this function maxCoins(nums) { const n = nums.length; const dp = Array(n + 2).fill(0).map(() => Array(n + 2).fill(0)); const balloons = [1, ...nums, 1]; for (let len = 1; len

[@kashishsharma6809]

oh god! such a hard ques. still don't know how will this recursive func will cover all the cases.

[@rhapsody9442]

For those who get a TLE, try to add a @lru_cache(None) before the dfs function. Though this may be opportunistic, but it does work for me :) Got this from a leetcode discuss but I cannot understand that solution. This neet solution is within my understanding.

[@derekmiller9520]

Wouldn't brute force be O(n!) complexity?

[@venkatarakesh1698]

Good explanation

[@Randomisticful]

I wish there were Java solutions using "proper English". But still, this does the job. Thanks!

[@joydeeprony89]

YOU ARE SUPER HUMAN, SAME AS MESSI IN FOOTBALL. THANKS FOR MAKING OUR LIFE EASIER SPECIALLY DEV LIKE ME WHO IS BELOW AVERAGE BUT HAVING AN AMBITION OF WORKING FOR TIER ONE PRODUCT COMPANY.

[@arnabpersonal6729]

very good approach but giving TLE

[@hanjiang9888]

it works with python 2 but not python 3 on leetcode. Does anyone meet the same problem?

[@syeds6789]

Thanks 😊

[@chowtuk]

It would be better to understand if this video is like others DP video which draw a grash to run the solution's algorithm , because this is quiet complex to understand, hard to implement how it actually run in my brain

[@wintersol9921]

Does anyone else get Time Limit Exceeded error when submitting it?

[@dk20can86]

This one nearly killed me 😮‍💨

[@gauravchauhan7412]

best video

[@m.y.7230]

Matrix Chain Multiplication would be easier approach

[@shouryansharma9441]

This solution is getting TLE

[@prathamhebbar5800]

This question makes me ask myself what is the meaning of life?

[@abhayphanse9509]

classic IT IS WHAT IT IZ problem

[@흘러가는대로-t7j]

Sooo clean

[@fdm6334]

This solution gives TLE now.

[@rackstar2]

this just throws a type error

[@Super111111111111Man]

Still not understand, help!

[@Rohan-hj9gg]

The solution does not work for the last test case.

[@sushantrocks]

Smells like matrix chain mult

[@darshanputtaswamy3199]

Yep, I smelt the same

[@joshithmurthy6209]

Most crip explaination on youtube

[@TankNSSpank]

genius

[@Philgob]

Dafuq is this

[@dataman4503]

Meticulous explanation...

[@shrn]

Why is the solution so simple?

[@Mnogarithm]

[@ChinmayAnaokar-xm4ci]

C# Implementation of above code with all test cases passed public class Solution { public int MaxCoins(int[] nums) { List lst = nums.ToList(); lst.Insert(0, 1); lst.Insert(lst.Count, 1); int count = lst.Count; int[,] dp = new int[count, count]; return DFS(1,lst.Count-2,dp,lst); } private int DFS(int l,int r,int [,] dp,Listnums) { if (l > r) return 0; if (dp[l, r] != 0) return dp[l, r]; dp[l, r] = 0; for(int i=l;i< r+1;i++) { int coins = nums[l - 1] * nums[i] * nums[r + 1]; coins = coins + DFS(l, i - 1, dp, nums) + DFS(i+1, r, dp, nums); dp[l, r] = Math.Max(dp[l, r], coins); } return dp[l, r]; } }

[@indrajitbagchi7313]

its matrix chain multiplication in disguise

[@shaamidrees6036]

Thanks