NESTED LIST WEIGHT SUM | LEETCODE # 339 | PYTHON BFS SOLUTION

[@aaditya_87]

when r u getting outta da hood , theres always a siren noise😂😂

[@worldrecordegg-g7y]

meta nyc

[@kapilrules]

extend is key here. thank you very much @Cracking FAANG, You are super awesome !!

[@manoelramon8283]

simpler version: from collections import deque class Solution: def depthSum(self, nestedList: List[NestedInteger]) -> int: """ :type nestedList: List[NestedInteger] :rtype: int """ # element and level (1 for all of theem at the beginning) q = deque([e , 1] for e in nestedList) level = 1 total = 0 while q: e,level = q.popleft() if e.isInteger(): #integer total += e.getInteger() * level else: #list lst = e.getList() for list_item in lst: #extract the numbers and increase the level q.append([list_item, level + 1]) return total

[@devdanlight]

Hey 0ms BEATS 100% recurisve solution: class Solution: def depthSum(self, nestedList: List[NestedInteger]) -> int: def calculate_sum(nested, depth): total = 0 for ni in nested: if ni.isInteger(): # If it's an integer, multiply it by its depth and add to total total += ni.getInteger() * depth else: # If it's a list, recursively calculate the sum for the nested list total += calculate_sum(ni.getList(), depth + 1) return total # Start the recursive calculation from depth 1 return calculate_sum(nestedList, 1)

[@Voidwanderer571]

4:50 all the 2*2 you wrote should be 2*1

[@Spyro-kt8gy]

Which data structure did they use to represent the nested list in C++? I can't see it since the question is Premium.

[@sarayarmohammadi3376]

Thank you

[@cc-to2jn]

never knew u could do this using bfs, honestly much easier lol

[@omi_naik]

DFS Solution class Solution: def __init__(self): self.suml=0 def depthSum(self, nestedList: List[NestedInteger]) -> int: # Start DFS with depth 1 self.helperdfs(nestedList, 1) return self.suml def helperdfs(self, nestedList, depth): #print(nestedList) for i in nestedList: if i.isInteger(): # Add integer value multiplied by depth self.suml += i.getInteger() * depth else: # Recur for the nested list with increased depth self.helperdfs(i.getList(), depth + 1)

[@ye7841]

it's really helpful, thank you!

[@crackfaang]

No problem! Make sure to subscribe and let me know if there’s any videos you’d like to see

[@jianingli7542]

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?

[@crackfaang]

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

[@pat777b]

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

[@a2m2tkyo]

7:18 same

[@kingskull619]

why not recursive?

[@pat777b]

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.