NESTED LIST WEIGHT SUM | LEETCODE # 339 | PYTHON BFS SOLUTION
Vložit
- čas přidán 6. 05. 2022
- In this video we are solving a popular Facebook interview question: Nested List Weight Sum (Leetcode # 339(.
This is a weird problem because we aren't given the data outright but rather given to us as part of a NestedList class that we need to interact with. Nothing crazy for the solution though, a standard BFS will solve this question beautifully. - Věda a technologie
when r u getting outta da hood , theres always a siren noise😂😂
Your videos are really helpful. Thank you for helping everyone. Video explanations are much easier and faster to understand than reading solutions in Leetcode discuss section. Just a feedback - Most people used Neetcode as their first choice. Most people don't have time to go to different channels for a particular problem. So if a particular problem is on Neetcode, other channels won't get much views for that problem. Please solve Top recent Amazon, Meta, Google questions which are not on Neetcode, so that people will come to you channel e.g. LCA of Binary Tree III - Top Facebook question not on Neetcode. If possible try to match drawing standards of Neetcode. Please design 14 DSA Patterns Template if possible. Thanks!
I very much agree with you! I use Neetcode for Blind75 related questions, and Cracking FAANG for top FAANG related questions, and the latter is usually my go to. Highly suggest dominating the top questions for FAANG.
it's really helpful, thank you!
No problem! Make sure to subscribe and let me know if there’s any videos you’d like to see
Which data structure did they use to represent the nested list in C++? I can't see it since the question is Premium.
4:50 all the 2*2 you wrote should be 2*1
Why is time complexity O(n). We need to visit n element in the nestedList and each element could have up to n level depth, wouldn't that gives us O(n^2) for time complexity?
N = the total number of distinct items in the nested list provided.
list = [1, 2, 3, 4, 5, 6, 7, 8, 9] has the same number of elements as [1, [2, [3, 4, [ 5, 6, 7, 8, [9]]]]]]. You are still processing a total of 9 numbers. It would be N^2 if at each level you then needed to process the array again somehow
@@crackfaang
I think another way to explain it is if you look at the parameters of the problem, you notice that depth has an upper bound of 50. Thus, the depth factor can be thought of as a constant multiplier and should not be considered when counting time complexity.
of course, the total number of integers can far exceed 50 with these constraints.
why not recursive?
he said he wants to avoid stack overflow. imo, the leetcode's problem parameters state that the maximum depth is 50 so there's no need to worry about stackoverflow. however, do note that the interviewer could alter the leetcode question. if the interviewer makes the maximum depth much bigger after a clarifying question, you should do the breadth first search solution to avoid stackoverflow. but if the interviewer keeps the maximum depth low, i'd go with a recursive dfs.
imo, it's good to have both solutions in mind and choose the one that's most appropriate to what the interviewer wants.