NUHMAN.com

Introduction

In LeetCode 339: Nested List Weight Sum, you're asked to compute the sum of all integers in a nested list, where each integer is weighted by its depth in the structure. This problem is a perfect fit for recursive depth-first search (DFS) because it naturally follows a tree-like structure.

Problem Statement

You are given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other lists. The depth of an integer is the number of lists that enclose it. Return the sum of all integers in the list weighted by their depth.

Example

python

Input: [[1,1],2,[1,1]]
Output: 10

Explanation:
- 1 and 1 at depth 2: 1×2 + 1×2 = 4
- 2 at depth 1: 2×1 = 2
- 1 and 1 at depth 2 again: 1×2 + 1×2 = 4
Total = 4 + 2 + 4 = 10

Understanding the Problem

This problem involves recursion through nested structures. At every level:

• If the element is an integer, we multiply it by the current depth.
• If the element is a list, we recurse deeper, increasing the depth by 1.

✅ Python Code: Recursive DFS Approach

LeetCode provides a custom interface NestedInteger. You can call:

• isInteger() → returns True if it's a single integer
• getInteger() → gets the integer value
• getList() → gets the nested list

Here's how you can solve it:

python

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nlist, depth):
            total = 0
            for ni in nlist:
                if ni.isInteger():
                    total += ni.getInteger() * depth
                else:
                    total += dfs(ni.getList(), depth + 1)
            return total
        
        return dfs(nestedList, 1)

🧠 Step-by-Step Breakdown

Let’s say you have:

python

nestedList = [[1, [4, [6]]]]

It gets interpreted as:

• 1 at depth 2 → 1 × 2 = 2
• 4 at depth 3 → 4 × 3 = 12
• 6 at depth 4 → 6 × 4 = 24

Total = 2 + 12 + 24 = 38

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(d)

Where:

• n is the total number of elements (including all nested ones),
• d is the maximum depth due to recursion stack.

🔄 BFS Alternative (Iterative Approach)

You can also use a queue to perform level-order traversal with BFS:

python

from collections import deque

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        queue = deque([(ni, 1) for ni in nestedList])
        total = 0

        while queue:
            ni, depth = queue.popleft()
            if ni.isInteger():
                total += ni.getInteger() * depth
            else:
                for child in ni.getList():
                    queue.append((child, depth + 1))
        
        return total

💡 Key Takeaways

• Great example of DFS on nested structures.
• Emphasizes recursion depth and how to carry context (depth) during traversal.
• Applies in real-world scenarios like parsing JSON or XML trees.

✅ Conclusion

LeetCode 339: Nested List Weight Sum provides a clean application of recursion, ideal for demonstrating tree or graph traversal logic. It sharpens your understanding of nested data structures and prepares you for more advanced problems like flattening nested lists or weighted sum variants.