Burst Baloons - Dynamic Programming - Leetcode 312 - Python
Vložit
- čas přidán 23. 07. 2024
- 🚀 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. - Věda a technologie
💡 DP Playlist: czcams.com/video/73r3KWiEvyk/video.html
Just wanted to say that your videos are the best Leetcode question explanations on CZcams by a long shot in my opinion.
Thanks and keep going!
Thanks Umbreon, you were always my favorite Eeveelution!
@@NeetCode lol
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
I hope no one gets discouraged while trying to get through this one. I'm almost there, lmao.
I was being so discourged while watching this video lol (I mean, NeetCode's explanation was excellent. This problem is just god damn hard)
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.
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
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
Can I have that 2^n solution please .
@@vinayak186f3 It's the same solution without dp
Bruteforce isn't 2^n, it's n^n, I think that's what you meant.
If you use @cache decorator it can pass.
@@MrPanthershah Brute force would be to generate all permutations, which is N!, which is asymptomatically less than N^N per Stirling's formula
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.
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]
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;
}
}
Could please explain why this works ?
this did not work for me
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
Thanks @bram. It worked by changing dict to 2D list
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?
3:58 I think the complexity would be n! (you get one less item on each level of the tree)
yes
yes, that solution basically generates all the permutations, which is n!
Fantastic explanation man! Keep up the great work
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?
Same...
it is more efficient - less overhead in computation which leads to it barely being accepted.
I did it bottom up and worked like a charm first try ✨️
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]
Specially, in JS, without 2d matrix cache, it got a TLE.
Thanks
What made you to not check l == r instead go with l > r as the base condition?
Could you please explain
Thanks for this, can we have video for palindrome partitioning (MCM variation)
I watch every LeetCode video of yours!
great explanation, keep it up mate :)
This is brilliant!
Awesome solution!
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!
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 ❤❤❤❤
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?
It's TLE-ing on the 69/70th case now
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.
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 😢
@@VarunMittal-viralmutant that's a bar raiser
@@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.
This is a crazy question
What is the need to initialize dp[(l,r)] to 0 and then update it as max of 0 and the newly computed value?
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
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.
Best explanation I ever found on youtube
Glad it was helpful!
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!
Does anyone else get Time Limit Exceeded error when submitting it?
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?"
great insight Houman!
But before deciding to look for possible subproblem, how can we intuitively conclude that this is a dp problem?
This looks like a variation of MCM. Is my intuition correct?
I think the time complexity of brute force will be n! Right?
Thanks 😊
Sooo clean
Thanks
Good explanation
I got TLE with the same code rip
Is there a list of problems on leetcode which fall under this category?
Where you able to find?
oh god! such a hard ques. still don't know how will this recursive func will cover all the cases.
Best of the best❤
why the range is r+1 in L13???
it works with python 2 but not python 3 on leetcode. Does anyone meet the same problem?
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?
@@numbtubeyou Understood, thanks
there should be a counter for the time neetcode said "pop" in this video 😂
fck, there is no way I could think this in an interview
me neither probably, im sure 90% of interviewers would give you a hint tho.
@@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.
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?
Well, we don't really care about the specific constants and thereby it is O(N^2) subarrays.
the most unsatisfying video from neetcode
This one nearly killed me 😮💨
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 💪
Your voice is sounds like "Hello everyone, this is your daily dose of internet"
best video
I would assume that the interviewer wanted to fail you if they ask you this question in interview.
lol me too
Wouldn't brute force be O(n!) complexity?
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
MAXIMUM PROFIT IN JOB SCHEDULING?
dito
genius
I wish there were Java solutions using "proper English". But still, this does the job. Thanks!
Still not understand, help!
This is one of those problems where I'm just going to hope I don't get it.
very good approach but giving TLE
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
Smells like matrix chain mult
Yep, I smelt the same
A moment of silence for those who got this question in an interview (bonus points for it being the first)
The solution does not work for the last test case.
Matrix Chain Multiplication would be easier approach
this just throws a type error
classic IT IS WHAT IT IZ problem
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.
This solution is getting TLE
This solution gives TLE now.
Most crip explaination on youtube
Meticulous explanation...
Why is the solution so simple?
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.
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];
}
}
Thanks