Nested List weight Sum

339.Nested List Weight Sum

Depth First Search

Recursion

Problem Statement:

Given a nested list of integers, return 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.

Example:

Input:

[[1,1],2,[1,1]]

→

Output:

10

Algorithm:

1. Use DFS to traverse nested structure
2. Track depth at each level
3. Multiply integers by their depth
4. Recursively process nested lists

Complexity:

Time: O(N) | Space: O(D) where D is max depth

Java Solution:

public int depthSum(List nestedList) {
    return dfs(nestedList, 1);  // Start with depth 1
}

public int dfs(List list, int depth) {
    int sum = 0;

    for (NestedInteger nest : list)
        if (nest.isInteger())  // If integer, add to sum with weight
            sum += nest.getInteger() * depth;
        else  // If list, recurse with increased depth
            sum += dfs(nest.getList(), depth + 1);
    
    return sum;
}

Python Solution:

def depthSum(self, nestedList: List[NestedInteger]) -> int:
    def dfs(nested_list: List[NestedInteger], depth: int) -> int:
        total = 0
        
        for nested in nested_list:
            if nested.isInteger():  # Base case: found integer
                total += nested.getInteger() * depth
            else:  # Recursive case: nested list
                total += dfs(nested.getList(), depth + 1)
                
        return total
    
    return dfs(nestedList, 1)

C++ Solution:

class Solution {
public:
    int depthSum(vector& nestedList) {
        return dfs(nestedList, 1);
    }
    
private:
    int dfs(vector& list, int depth) {
        int sum = 0;
        
        for(const auto& nest : list) {
            if(nest.isInteger())  // Found integer
                sum += nest.getInteger() * depth;
            else {  // Process nested list
                auto inner = nest.getList();
                sum += dfs(inner, depth + 1);
            }
        }
        
        return sum;
    }
};