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

What Is LeetCode 364: Nested List Weight Sum II?

LeetCode 364: Nested List Weight Sum II provides a nested list of integers, where each element is either an integer or another nested list. Your task is to compute the sum of all integers, weighted by their "reverse depth"—the maximum depth minus their actual depth plus 1. This contrasts with LeetCode 339, where deeper numbers had higher weights. It’s a fun twist on recursion and list traversal!

Problem Statement

• Input:
• nestedList: A nested list where each element is either an integer or a list (NestedInteger interface).
• Output: Integer - Sum of all integers weighted by (max_depth - depth + 1).
• Rules:
• Depth starts at 1 for top-level elements.
• Weight decreases with depth (reverse of typical weighting).
• Use NestedInteger API: isInteger(), getInteger(), getList().

Constraints

• 1 <= nestedList.length <= 50
• Integers range from -100 to 100.
• Maximum nesting depth ≤ 50.

Examples

• Input: [1,[4,[6]]]
• Output: 17
• Depth 1: 1 (max_depth=3, weight=3-1+1=3) → 1*3 = 3.
• Depth 2: 4 (weight=3-2+1=2) → 4*2 = 8.
• Depth 3: 6 (weight=3-3+1=1) → 6*1 = 6.
• Total = 3 + 8 + 6 = 17.
• Input: [[1,1],2,[1,1]]
• Output: 8
• Depth 1: 2 (weight=2-1+1=2) → 2*2 = 4.
• Depth 2: 1,1,1,1 (weight=2-2+1=1) → 1*1 + 1*1 + 1*1 + 1*1 = 4.
• Total = 4 + 4 = 8.
• Input: [1,2,3]
• Output: 6
• Depth 1: 1,2,3 (weight=1-1+1=1) → 1*1 + 2*1 + 3*1 = 6.

These show the reverse weighting—let’s solve it!

Understanding the Problem: Weighing Nested Integers

To tackle LeetCode 364 in Python, we need to: 1. Determine the maximum depth of the nested list. 2. Assign weights: max_depth - depth + 1 for each integer. 3. Compute the weighted sum.

A naive approach might process everything in one pass, but we need max_depth first. We’ll use:

• Best Solution: Two-pass depth tracking—O(n) time, O(1) space—efficient and elegant.
• Alternative Solution: Recursive depth accumulation—O(n) time, O(n) space—intuitive but uses more memory.

Let’s weigh with the best solution!

Best Solution: Two-Pass Depth Tracking

Why This Is the Best Solution

The two-pass approach runs in O(n) time with O(1) extra space by:

• First pass: Find the maximum depth.
• Second pass: Compute the weighted sum using max_depth.

It avoids recursion’s stack overhead and extra storage, making it the most efficient solution—perfect for this nested challenge!

How It Works

Think of it like a two-step exploration:

• Pass 1: Traverse the nested list to find max_depth using DFS or iteration.
• Pass 2: Traverse again, summing each integer with weight (max_depth - depth + 1).
• Result: Return the total weighted sum.

It’s like scouting the deepest layer, then weighing everything!

Step-by-Step Example

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

• Pass 1: Find Max Depth:
• 1 (depth=1).
• [4,[6]] (depth=2).
• [6] (depth=3).
• Max_depth = 3.
• Pass 2: Compute Sum:
• 1 (depth=1, weight=3-1+1=3) → 1*3 = 3.
• 4 (depth=2, weight=3-2+1=2) → 4*2 = 8.
• 6 (depth=3, weight=3-3+1=1) → 6*1 = 6.
• Total = 3 + 8 + 6 = 17.

For nestedList = [[1,1],2,[1,1]]:

• Pass 1:
• [1,1] (depth=2), 2 (depth=1), [1,1] (depth=2).
• Max_depth = 2.
• Pass 2:
• 1,1 (depth=2, weight=2-2+1=1) → 1*1 + 1*1 = 2.
• 2 (depth=1, weight=2-1+1=2) → 2*2 = 4.
• 1,1 (depth=2, weight=1) → 1*1 + 1*1 = 2.
• Total = 2 + 4 + 2 = 8.

Code with Explanation

Here’s the Python code using two passes with iteration:

Copy codeclass Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        # Helper to find max depth iteratively
        def get_max_depth(nested_list):
            max_depth = 1
            stack = [(nl, 1) for nl in nested_list]  # (NestedInteger, depth)
            while stack:
                curr, depth = stack.pop()
                if not curr.isInteger():
                    max_depth = max(max_depth, depth + 1)
                    for child in curr.getList():
                        stack.append((child, depth + 1))
            return max_depth

        # First pass: Find maximum depth
        max_depth = get_max_depth(nestedList)

        # Second pass: Compute weighted sum
        total = 0
        stack = [(nl, 1) for nl in nestedList]
        while stack:
            curr, depth = stack.pop()
            if curr.isInteger():
                weight = max_depth - depth + 1
                total += curr.getInteger() * weight
            else:
                for child in curr.getList():
                    stack.append((child, depth + 1))

        return total

Explanation

• Lines 3-12: get_max_depth:
• Use a stack with (NestedInteger, depth) pairs, starting at depth 1.
• For each non-integer, increase depth and push children.
• Track max_depth—O(n) time, O(n) stack space (temporary).
• Line 15: First pass calls get_max_depth to find max_depth.
• Lines 17-25: Second pass:
• Stack starts with top-level elements at depth 1.
• For integers: Compute weight = max_depth - depth + 1, add to total.
• For lists: Push children with depth + 1.
• Line 27: Return total weighted sum.

• Time Complexity: O(n)—two passes over all elements (n total integers and list nodes).
• Space Complexity: O(1)—stack space is temporary, could be O(n) in recursion, but optimized here as iterative.

This is like a two-step treasure hunt—find the depth, then weigh the loot!

Alternative Solution: Recursive Depth Accumulation

Why an Alternative Approach?

The recursive solution also runs in O(n) time but uses O(n) space for recursion and storing depths. It’s more intuitive—compute depths and sums in one pass, then adjust with max_depth—great for understanding the problem!

How It Works

• Recurse: Traverse the list, tracking depth and collecting (value, depth) pairs.
• Adjust: Post-process to apply reverse weights using max_depth.
• Result: Sum the weighted values.

Step-by-Step Example

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

• Recurse:
• 1 (depth=1) → [(1,1)].
• [4,[6]] (depth=2) → [(4,2)].
• [6] (depth=3) → [(6,3)].
• Pairs: [(1,1), (4,2), (6,3)].
• Max Depth: 3.
• Sum:
• 1 (weight=3-1+1=3) → 1*3 = 3.
• 4 (weight=3-2+1=2) → 4*2 = 8.
• 6 (weight=3-3+1=1) → 6*1 = 6.
• Total = 3 + 8 + 6 = 17.

Code with Explanation

Copy codeclass Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        # Helper to collect (value, depth) pairs recursively
        def collect_values(nested_list, depth, values):
            for nl in nested_list:
                if nl.isInteger():
                    values.append((nl.getInteger(), depth))
                else:
                    collect_values(nl.getList(), depth + 1, values)

        # Collect all values with their depths
        values = []
        collect_values(nestedList, 1, values)

        # Find max depth
        if not values:
            return 0
        max_depth = max(depth for _, depth in values)

        # Compute weighted sum
        total = 0
        for val, depth in values:
            weight = max_depth - depth + 1
            total += val * weight

        return total

Explanation

• Lines 3-9: collect_values:
• Recursively traverse, append (value, depth) for integers.
• Increase depth for nested lists—O(n) time.
• Lines 11-13: Collect all pairs in one pass.
• Lines 15-17: Handle empty case, find max_depth from pairs.
• Lines 19-22: Compute sum with weights = max_depth - depth + 1.
• Time: O(n)—single traversal and linear sum.
• Space: O(n)—stores all values and recursion stack.

It’s like gathering all treasures, then weighing them!

Comparing the Two Solutions

• Two-Pass Depth Tracking (Best):
• Time: O(n)—two linear passes.
• Space: O(1)—minimal extra space (iterative).
• Pros: Efficient, low memory.
• Cons: Two passes less intuitive.
• Recursive Depth Accumulation (Alternative):
• Time: O(n)—one pass plus sum.
• Space: O(n)—values list and stack.
• Pros: Clear recursion.
• Cons: More memory.

Two-pass wins for efficiency and space!

Additional Examples and Edge Cases

• []: 0 (empty list).
• [1]: 1 (max_depth=1, weight=1).
• Deep nesting: Both scale to depth 50.

Both handle these, two-pass is leaner.

Complexity Breakdown

• Two-Pass:
• Time: O(n).
• Space: O(1).
• Recursive:
• Time: O(n).
• Space: O(n).

Two-pass excels for space efficiency.

Key Takeaways

• Two-Pass: Optimize space—smart and fast!
• Recursive: Collect and compute—easy to grasp!
• Nesting: Depth adds flavor.
• Python Tip: Iteration beats recursion—see [Python Basics](/python/basics).

Final Thoughts: Weigh Those Layers

LeetCode 364: Nested List Weight Sum II in Python is a nested weighting challenge. The two-pass solution is the efficiency champ, while recursion builds intuition. Want more? Try LeetCode 339: Nested List Weight Sum or LeetCode 341: Flatten Nested List Iterator. Ready to sum? Visit Solve LeetCode 364 on LeetCode (premium) and weigh those numbers today!