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
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
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.
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; } }
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
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.
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?
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 😢
@@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.
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?"
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 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!
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?
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?
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.
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 💪
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?
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?
@@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.
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
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
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.
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.
@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.
💡 DP Playlist: ruclips.net/video/73r3KWiEvyk/видео.html
Just wanted to say that your videos are the best Leetcode question explanations on RUclips 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
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
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.
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
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!
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
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.
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 ✨️
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
@@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.
I watch every LeetCode video of yours!
best simple explanation, i was not getting idea before watching this
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
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?
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!
Best explanation I ever found on youtube
Glad it was helpful!
Thanks for this, can we have video for palindrome partitioning (MCM variation)
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!
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?
It's TLE-ing on the 69/70th case now
This is a crazy question
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 ❤❤❤❤
Is there a way to solve this without using memoization, like the regular DP?
Thanks, Neet!
What made you to not check l == r instead go with l > r as the base condition?
Could you please explain
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
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.
This looks like a variation of MCM. Is my intuition correct?
I think the time complexity of brute force will be n! Right?
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 💪
the most unsatisfying video from neetcode
I got TLE with the same code rip
Fantastic explanation man! Keep up the great work
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?
why the range is r+1 in L13???
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.
Is there a list of problems on leetcode which fall under this category?
Where you able to find?
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 didn't get why did you compute max operation?
This is one of those problems where I'm just going to hope I don't get it.
I would assume that the interviewer wanted to fail you if they ask you this question in interview.
lol me too
Thanks
Your voice is sounds like "Hello everyone, this is your daily dose of internet"
great explanation, keep it up mate :)
MAXIMUM PROFIT IN JOB SCHEDULING?
dito
oh god! such a hard ques. still don't know how will this recursive func will cover all the cases.
I think its time to solve this question again with a iterative approach
Awesome solution!
A moment of silence for those who got this question in an interview (bonus points for it being the first)
I recently got this as the first question in the second round 😢
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
This is brilliant!
Wouldn't brute force be O(n!) complexity?
there should be a counter for the time neetcode said "pop" in this video 😂
Best of the best❤
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
Good explanation
I wish there were Java solutions using "proper English". But still, this does the job. Thanks!
best video
very good approach but giving TLE
Matrix Chain Multiplication would be easier approach
it works with python 2 but not python 3 on leetcode. Does anyone meet the same problem?
Thanks 😊
this just throws a type error
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.
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
Sooo clean
This one nearly killed me 😮💨
Does anyone else get Time Limit Exceeded error when submitting it?
This question makes me ask myself what is the meaning of life?
This solution gives TLE now.
classic IT IS WHAT IT IZ problem
Still not understand, help!
The solution does not work for the last test case.
Smells like matrix chain mult
Yep, I smelt the same
genius
Most crip explaination on youtube
Dafuq is this
@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.
You are not correct. Subsequences are important in the subproblem and its 2^n subsequences.
Meticulous explanation...
Why is the solution so simple?
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