Nested List Weight Sum
Medium
Nested List Weight Sum
Given a nested list of integers, calculate the sum of all integers in the list weighted by their depth. Each element is either an integer or a list, whose elements may also be integers or other lists.
The depth is defined as the number of lists it is inside. For example, the depth of an integer in the list [1,2] is 1, while the depth of an integer in the list [[1],2] is 2 for the integer 1 and 1 for the integer 2.
Example 1:
Input: [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 4 * 2 + 1 * 2 = 10
Example 2:
Input: [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1 * 1 + 4 * 2 + 6 * 3 = 27
Could you implement a function that takes a nested list of integers and returns the sum of all integers in the list weighted by their depth? Discuss the time and space complexity of your approach. How would you handle edge cases such as an empty list or extremely deep nesting?
Solution
Nested List Weight Sum
This problem asks us to calculate the weighted sum of integers within a nested list. The weight of an integer is determined by its depth within the nested structure. Let's explore different approaches to solve this problem.
Naive Approach: Recursion
A straightforward approach is to use recursion. We can traverse the nested list, and for each integer we encounter, we multiply it by its depth and add it to the total sum. For nested lists, we recursively call the function, incrementing the depth.
Code (Python)
def depthSum(nestedList, depth=1):
total = 0
for item in nestedList:
if isinstance(item, int):
total += item * depth
else:
total += depthSum(item, depth + 1)
return total
Time Complexity
O(N), where N is the total number of integers in the nested list (including duplicates due to nesting).
Space Complexity
O(D), where D is the maximum depth of the nested list, due to the recursive call stack.
Optimal Approach: Iterative with Stack (DFS)
An iterative approach using a stack can avoid the overhead of recursion and potential stack overflow issues for deeply nested lists. We use a stack to keep track of the nested lists and their corresponding depths.
Code (Python)
def depthSum(nestedList):
stack = [(nestedList, 1)] # (list, depth)
total = 0
while stack:
nested_list, depth = stack.pop()
for item in nested_list:
if isinstance(item, int):
total += item * depth
else:
stack.append((item, depth + 1))
return total
Time Complexity
O(N), where N is the total number of integers in the nested list.
Space Complexity
O(D), where D is the maximum depth of the nested list. In the worst case (a very skewed tree), the stack might hold elements up to the maximum depth.
Edge Cases
- Empty List: If the input list is empty, the sum should be 0. Both recursive and iterative methods handle this correctly.
- List with only Integers: The algorithm should correctly compute the sum with a depth of 1 for all integers.
- Deeply Nested Lists: The iterative approach is generally preferred for very deeply nested lists to avoid potential stack overflow issues associated with recursion.
- Mixed Integers and Lists: The algorithm should gracefully handle lists containing both integers and other lists.
