# LeetCode 364: Nested List Weight Sum II

## Problem Restatement

We are given a nested list.

Each element is either:

```text
an integer
```

or:

```text
a list containing integers or more nested lists
```

We need to return the weighted sum of all integers.

This problem uses inverse depth weights.

That means integers closer to the top have larger weight, and integers at the deepest level have weight `1`.

The official statement says this differs from the previous Nested List Weight Sum problem: here the leaf-level integers have weight `1`, while root-level integers have the largest weight. For example, `[1,[4,[6]]]` gives `1 * 3 + 4 * 2 + 6 * 1 = 17`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nestedList`, a list of `NestedInteger` objects |
| Output | Integer inverse depth weighted sum |
| Integer weight | `maxDepth - depth + 1` |
| Deepest integers | Weight `1` |
| Top-level integers | Largest weight |

Example function shape:

```python
def depthSumInverse(nestedList: list[NestedInteger]) -> int:
    ...
```

LeetCode provides the `NestedInteger` interface. We should not implement or assume its internals.

It supports these methods:

```python
isInteger()
getInteger()
getList()
```

## Examples

Example 1:

```python
nestedList = [[1, 1], 2, [1, 1]]
```

The integers are:

| Integer | Depth | Weight |
|---:|---:|---:|
| `1` | `2` | `1` |
| `1` | `2` | `1` |
| `2` | `1` | `2` |
| `1` | `2` | `1` |
| `1` | `2` | `1` |

So the answer is:

```python
1 + 1 + 2 * 2 + 1 + 1 = 8
```

Example 2:

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

The deepest integer is `6`, so the maximum depth is `3`.

| Integer | Depth | Weight | Contribution |
|---:|---:|---:|---:|
| `1` | `1` | `3` | `3` |
| `4` | `2` | `2` | `8` |
| `6` | `3` | `1` | `6` |

Answer:

```python
17
```

## First Thought: Find Max Depth, Then Sum

A direct solution uses two DFS passes.

First pass:

```text
find the maximum depth
```

Second pass:

```text
sum each integer times maxDepth - depth + 1
```

This works and is easy to prove.

But there is a cleaner one-pass level-order idea.

## Key Insight

Instead of computing the maximum depth directly, process the nested list level by level.

At each level, keep a running sum of all integers seen so far.

Then add that running sum to the answer once per level.

Why does this create inverse depth weights?

Consider:

```python
[1, [4, [6]]]
```

Process by levels:

| Level | Integers found | Running unweighted sum | Add to answer |
|---:|---|---:|---:|
| `1` | `1` | `1` | `1` |
| `2` | `4` | `1 + 4 = 5` | `5` |
| `3` | `6` | `1 + 4 + 6 = 11` | `11` |

Total:

```python
1 + 5 + 11 = 17
```

The top-level `1` is included at levels `1`, `2`, and `3`, so it is counted `3` times.

The `4` is included at levels `2` and `3`, so it is counted `2` times.

The `6` is included only at level `3`, so it is counted `1` time.

That exactly matches inverse depth weighting.

## Algorithm

Use BFS by levels.

Maintain:

| Variable | Meaning |
|---|---|
| `current_level` | The list of `NestedInteger` objects at the current depth |
| `unweighted` | Sum of all integers seen up to this level |
| `weighted` | Final answer being accumulated |

Steps:

1. Set `current_level = nestedList`.
2. Set `unweighted = 0`.
3. Set `weighted = 0`.
4. While `current_level` is not empty:
   - Create `next_level = []`.
   - For each item in `current_level`:
     - If it is an integer, add it to `unweighted`.
     - Otherwise, append its children to `next_level`.
   - Add `unweighted` to `weighted`.
   - Move to `next_level`.
5. Return `weighted`.

## Correctness

The BFS loop processes the nested structure one depth level at a time.

When an integer appears at depth `d`, it is first added to `unweighted` while processing level `d`.

After that, `unweighted` is added to `weighted` once for every remaining level, including level `d`.

If the maximum depth is `D`, then an integer at depth `d` contributes to `weighted` exactly:

```python
D - d + 1
```

times.

That is precisely the inverse depth weight required by the problem.

Every integer is added to `unweighted` exactly once, when its own level is processed. Lists only pass their children to the next level and do not directly affect the sum.

Therefore, the final `weighted` value equals the required inverse depth weighted sum.

## Complexity

Let `N` be the total number of `NestedInteger` objects, including integers and lists.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(N)` | Each nested element is visited once |
| Space | `O(W)` | BFS stores one level at a time, where `W` is the maximum level width |

In the worst case, `W` can be `O(N)`.

## Implementation

```python
class Solution:
    def depthSumInverse(self, nestedList: list["NestedInteger"]) -> int:
        current_level = nestedList

        unweighted = 0
        weighted = 0

        while current_level:
            next_level = []

            for item in current_level:
                if item.isInteger():
                    unweighted += item.getInteger()
                else:
                    next_level.extend(item.getList())

            weighted += unweighted
            current_level = next_level

        return weighted
```

## Code Explanation

We start from the top-level list:

```python
current_level = nestedList
```

The variable `unweighted` stores the sum of every integer seen so far:

```python
unweighted = 0
```

The variable `weighted` stores the final answer:

```python
weighted = 0
```

At each level, we prepare the next level:

```python
next_level = []
```

If an item is an integer, we add it to the running sum:

```python
if item.isInteger():
    unweighted += item.getInteger()
```

If an item is a list, we move its children to the next level:

```python
else:
    next_level.extend(item.getList())
```

After finishing the level, we add `unweighted` to `weighted`:

```python
weighted += unweighted
```

This is the key line.

It makes earlier integers count again at deeper levels.

Then we move downward:

```python
current_level = next_level
```

## Alternative Implementation: Two-Pass DFS

We can also solve the problem by first collecting values by depth.

```python
class Solution:
    def depthSumInverse(self, nestedList: list["NestedInteger"]) -> int:
        values = []

        def dfs(items: list["NestedInteger"], depth: int) -> None:
            if depth == len(values):
                values.append(0)

            for item in items:
                if item.isInteger():
                    values[depth] += item.getInteger()
                else:
                    dfs(item.getList(), depth + 1)

        dfs(nestedList, 0)

        answer = 0
        max_depth = len(values)

        for depth, level_sum in enumerate(values):
            weight = max_depth - depth
            answer += level_sum * weight

        return answer
```

This version is also correct. The BFS running-sum version is shorter and avoids explicitly computing weights.

## Testing

Because LeetCode provides `NestedInteger`, local testing needs a small mock class.

```python
class NestedInteger:
    def __init__(self, value=None):
        self.value = value
        self.children = []

    def isInteger(self):
        return self.value is not None

    def getInteger(self):
        return self.value

    def getList(self):
        return self.children

    def add(self, item):
        self.children.append(item)

def build(data):
    if isinstance(data, int):
        return NestedInteger(data)

    node = NestedInteger()
    for item in data:
        node.add(build(item))
    return node

def run_tests():
    s = Solution()

    assert s.depthSumInverse(build([[1, 1], 2, [1, 1]]).getList()) == 8

    assert s.depthSumInverse(build([1, [4, [6]]).getList()) == 17

    assert s.depthSumInverse(build([0]).getList()) == 0

    assert s.depthSumInverse(build([[-1], [2], [[3]]]).getList()) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[1,1],2,[1,1]]` | Standard example |
| `[1,[4,[6]]]` | Checks inverse weighting across 3 depths |
| `[0]` | Handles zero |
| `[[-1],[2],[[3]]]` | Handles negative values and mixed depths |