Burst Baloons - Dynamic Programming - Leetcode 312 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/burst-ba...
0:00 - Read the problem
4:13 - Intuition
13:15 - Drawing Explanation
16:55 - Coding Explanation
leetcode 312
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#burst #baloons #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@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

[@sarthuaksharma9609]

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

[@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)

[@numberonep5404]

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

[@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.

[@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

[@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

[@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.

[@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

[@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

[@SreyesSrinivasan]

Fantastic explanation man! Keep up the great work

[@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?

[@ahmedrebei8138]

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

[@vijayola7597]

yes

[@sk_4142]

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

[@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 ✨️

[@MrKB_SSJ2]

I watch every LeetCode video of yours!

[@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!

[@ammarqureshi2155]

great explanation, keep it up mate :)

[@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 ❤❤❤❤

[@Rohan-hj9gg]

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

[@VishalKumar-kr9me]

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

[@nathanx.675]

This is brilliant!

[@albertjtyeh53]

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

[@linli7049]

Awesome solution!

[@hwang1607]

This is a crazy question

[@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!

[@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?

[@ashwinnema06]

Best explanation I ever found on youtube

[@NeetCode]

Glad it was helpful!

[@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 😢

[@igorborovkov7011]

@@VarunMittal-viralmutant that's a bar raiser

[@VarunMittal-viralmutant]

@@igorborovkov7011 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.

[@forresthu6204]

Thanks

[@syeds6789]

Thanks 😊

[@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.

[@venkatarakesh1698]

Good explanation

[@user-th8dr3iu5g]

Sooo clean

[@mahedihassanrabby9553]

Best of the best❤

[@chenzhuo9]

I got TLE with the same code rip

[@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?

[@chowtuk]

the most unsatisfying video from neetcode

[@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 💪

[@gauravchauhan7412]

best video

[@akshay-kumar-007]

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

[@kashishsharma6809]

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

[@ameynaik2743]

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

[@DarkOceanShark]

Where you able to find?

[@sagarpotnis1215]

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

[@sauravgupta7415]

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

[@samarthtandale9121]

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

[@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

[@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?

[@user-dl1jb5vz6x]

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

[@wintersol9921]

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

[@dk20can86]

This one nearly killed me 😮‍💨

[@hanjiang9888]

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

[@user-lv2lm4wh6d]

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

[@dataman4503]

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

[@NeetCode]

lol me too

[@TankNSSpank]

genius

[@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

[@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.

[@milseq]

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

[@arnabpersonal6729]

very good approach but giving TLE

[@Randomisticful]

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

[@derekmiller9520]

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

[@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

[@user-ul9rs2ge7x]

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

[@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.

[@rackstar2]

this just throws a type error

[@m.y.7230]

Matrix Chain Multiplication would be easier approach

[@shouryansharma9441]

This solution is getting TLE

[@abhayphanse9509]

classic IT IS WHAT IT IZ problem

[@fdm6334]

This solution gives TLE now.

[@Rohan-hj9gg]

The solution does not work for the last test case.

[@Super111111111111Man]

Still not understand, help!

[@sushantrocks]

Smells like matrix chain mult

[@darshanputtaswamy3199]

Yep, I smelt the same

[@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.

[@joshithmurthy6209]

Most crip explaination on youtube

[@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]; } }

[@shaamidrees6036]

Thanks