LeetCode 339: Nested List Weight Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 339: Nested List Weight Sum?

In LeetCode 339: Nested List Weight Sum, you’re given a nested list where each element is either an integer or another nested list, and your task is to compute the sum of all integers, with each integer multiplied by its depth (1-based, from outermost level). For example, with [[1,1],2,[1,1]], the sum is 10 (12 + 12 + 21 + 12 + 1*2). This problem tests your ability to handle nested structures, connecting to concepts in LeetCode 341: Flatten Nested List Iterator.

Problem Statement

• Input: A nested list of integers and lists (NestedInteger objects with methods isInteger(), getInteger(), getList()).
• Output: An integer—the weighted sum of all integers by their depth.
• Rules:
• Depth starts at 1 for outermost level.
• Each integer’s value is multiplied by its depth.
• Nested lists can contain integers or more lists.

Constraints

• Number of elements (integers + lists): 1 to 50
• -100 <= integer value <= 100
• Maximum nesting depth: 50

Examples

• Input: [[1,1],2,[1,1]]
• Output: 10 (Depth 2: 1+1+1+1 = 4*2, Depth 1: 2*1 = 2, Total = 8+2)
• Input: [1,[4,[6]]]
• Output: 27 (Depth 1: 1*1, Depth 2: 4*2, Depth 3: 6*3, Total = 1+8+18)
• Input: [2]
• Output: 2 (Depth 1: 2*1)

Understanding the Problem: Weighing the Sums

To solve LeetCode 339: Nested List Weight Sum in Python, we need to traverse the nested list, track the depth of each integer, and compute the weighted sum. A naive approach—flattening the list first—could work but misses the elegance of handling depth directly. We’ll use:

• Best Solution (Recursive DFS): O(n) time, O(d) space—fast and natural (n = total elements, d = max depth).
• Alternative Solution (Iterative with Queue): O(n) time, O(n) space—clear but less intuitive.

Let’s start with the recursive DFS solution, explained in a beginner-friendly way.

Best Solution: Recursive DFS

Why This Is the Best Solution

The recursive DFS approach is the top choice for LeetCode 339 because it’s efficient—O(n) time, O(d) space—and naturally fits the nested structure, processing each element exactly once while tracking depth via recursion. It uses the NestedInteger interface to seamlessly handle integers and lists. It’s like digging through treasure boxes with a depth counter—smart and sleek!

How It Works

Think of this as a treasure diver:

• Step 1: Define DFS:
• Takes a nested list and current depth.
• Returns weighted sum for that subtree.
• Step 2: Process Each Element:
• If integer: Multiply by depth.
• If list: Recurse with depth + 1.
• Step 3: Sum Results:
• Add up all weighted values.
• Step 4: Why It Works:
• Recursion mirrors nesting.
• Depth increases correctly per level.

It’s like counting coins as you dive deeper!

Step-by-Step Example

Example: [[1,1],2,[1,1]]

• Depth 1:
• [1,1]: DFS([1,1], 2) = 1*2 + 1*2 = 4
• 2: 2*1 = 2
• [1,1]: DFS([1,1], 2) = 1*2 + 1*2 = 4
• Total: 4 + 2 + 4 = 10

Example: [1,[4,[6]]]

• Depth 1:
• 1: 1*1 = 1
• [4,[6]]: DFS([4,[6]], 2)
• 4: 4*2 = 8
• [6]: DFS([6], 3) = 6*3 = 18
• Total = 8 + 18 = 26
• Total: 1 + 26 = 27

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nested, depth):
            total = 0
            for item in nested:
                if item.isInteger():
                    total += item.getInteger() * depth  # Weight by depth
                else:
                    total += dfs(item.getList(), depth + 1)  # Recurse deeper
            return total

        return dfs(nestedList, 1)  # Start at depth 1

• Lines 3-9: DFS function:
• Takes list and current depth.
• For each item: if integer, multiply by depth; if list, recurse with depth+1.
• Line 11: Start DFS from root list at depth 1.
• Time Complexity: O(n)—visit each element once (n = total integers + lists).
• Space Complexity: O(d)—recursion stack (d = max depth).

This is like a depth-diving treasure hunter—fast and precise!

Alternative Solution: Iterative with Queue

Why an Alternative Approach?

The iterative approach—O(n) time, O(n) space—uses a queue to process the nested list level-by-level, tracking depth with each element. It’s more explicit and avoids recursion, making it a good alternative for understanding, though it uses more space. It’s like unpacking boxes layer-by-layer—clear but bulkier!

How It Works

Unpack with a queue:

• Step 1: Queue starts with (list, depth) pairs.
• Step 2: Process queue:
• If integer, add to sum with depth.
• If list, enqueue its elements with depth+1.
• Step 3: Sum all weighted values.

Step-by-Step Example

Example: [1,[4,[6]]]

• Queue: [([1,[4,[6]]], 1)]
• Step 1: Pop ([1,[4,[6]]], 1)
• 1*1 = 1, Enqueue ([4,[6]], 2)
• Step 2: Pop ([4,[6]], 2)
• 4*2 = 8, Enqueue ([6], 3)
• Step 3: Pop ([6], 3)
• 6*3 = 18
• Total: 1 + 8 + 18 = 27

Code for Iterative Approach

Copy codefrom collections import deque

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        queue = deque([(nestedList, 1)])  # (list, depth)
        total = 0

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

        return total

• Time Complexity: O(n)—process each element once.
• Space Complexity: O(n)—queue size.

It’s a layer-by-layer unpacker—vivid but heavier!

Comparing the Two Solutions

• Recursive DFS (Best):
• Pros: O(n) time, O(d) space, natural and fast.
• Cons: Recursive logic.
• Iterative with Queue (Alternative):
• Pros: O(n) time, O(n) space, explicit control.
• Cons: More space, less intuitive.

DFS wins for elegance and space.

Additional Examples and Edge Cases

• [[]]: 0.
• [1]: 1.
• [[1],[2]]: 5 (1*2 + 2*2).

Both handle these, but DFS is leaner.

Complexity Breakdown

• Recursive DFS: Time O(n), Space O(d).
• Iterative with Queue: Time O(n), Space O(n).

DFS is the clear choice.

Key Takeaways

• Recursive DFS: Dive deep—efficient!
• Iterative with Queue: Unpack step-by-step—clear!
• Python: Recursion and queues shine—see [Python Basics](/python/basics).
• Nesting: Depth adds weight.

Final Thoughts: Weigh the Treasure

LeetCode 339: Nested List Weight Sum in Python is a nested traversal gem. The recursive DFS solution offers speed and elegance, while the iterative queue approach provides a tangible baseline. Want more list challenges? Try LeetCode 341: Flatten Nested List Iterator or LeetCode 364: Nested List Weight Sum II. Ready to sum? Head to Solve LeetCode 339 on LeetCode (premium) and weigh those numbers today!