339. Nested List Weight Sum

Problem Statement

This problem gives you a nested list of integers called nestedList, where each element is represented by the NestedInteger interface. An element can be either:

• A single integer, or
• A list of more NestedInteger elements (which may themselves be integers or further lists).

Your task is to compute a depth-weighted sum of all integers contained anywhere inside this structure:

• The depth of an integer is the number of lists that contain it.
• An integer that appears at the top level (not inside any inner list) has depth 1.
• If an integer is inside one additional list, its depth is 2, and so on.

For every integer value x found in nestedList, you add x * depth(x) to the total. Finally, you return the total weighted sum as an integer.

Constraints:

• $ \leq$ nestedList.length $\leq $
• The values of the integers in the nested list is in the range $[−100,100]$.
• The maximum depth of any integer is less than or equal to $50$.

Examples

Optimal Solution: Breadth-first Traversal

The main idea behind this optimal solution is to compute the weighted sum directly while traversing the nested structure. The key observation is that depth increases one level at a time: elements visible at the outermost level have depth $1$, and elements discovered by opening those lists belong to depth $2$, then depth $3$, and so on.

Breadth-first traversal (BFS) matches this perfectly because it processes items level by level using a queue. By working level-by-level, you always know which depth you are currently handling, so each integer can be weighted correctly at the moment it is encountered. Lists themselves do not add to the sum, but they serve as gateways to nested elements; once a list is expanded, its contents belong to the next depth level and should be processed with a larger multiplier.

A useful way to preserve correct depth values is to treat each level as a separate “batch” of work. The queue holds the current batch, and measuring its size at the start of a level ensures that everything processed in that pass belongs to the same depth. Any elements discovered while expanding lists are added to the queue for the next batch, automatically shifting them to the next depth without needing to store explicit (value, depth) pairs. This keeps the solution clean and single-pass, with memory usage limited to the queue of pending elements rather than an extra flattened copy of the input. As a result, the algorithm stays a single pass over the nested structure, and the only extra memory it uses is the queue needed to hold elements waiting to be processed, rather than an additional flattened representation of the entire input.

Algorithmic Steps

The algorithm is implemented as follows:

1. Create a queue q.
2. Initialize q by adding every element from nestedList in it.
3. Set depth = 0 and total = 0.
4. While the q is not empty:
   1. Increment depth by 1.
   2. Set layerSize to the length of q.
   3. Start iterating over nestedList:
      1. Pop an element from q and store it in cur.
      2. If cur is an integer, add value * depth to total.
      3. Otherwise, push all elements of its inner list into q.
5. After iterating through , return the value of total.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 8

Python Implementation

Let’s implement the algorithm as discussed above:

from collections import deque

def depthSum(nestedList):
    """
    BFS level traversal:
    - each BFS "layer" corresponds to a depth value
    - integers contribute integer * depth when encountered
    """
    q = deque()

    # Start by queuing all top-level elements (these are at depth 1).
    for ni in nestedList:
        q.append(ni)

    total = 0
    depth = 0

    # Process layer by layer, increasing depth each time.
    while q:
        depth += 1
        layerSize = len(q)

        # Process exactly one depth layer.
        for _ in range(layerSize):
            cur = q.popleft()

            if cur.isInteger():
                # Integer contributes its value times the current depth.
                total += cur.getInteger() * depth
            else:
                # List contributes its children to the next layers.
                for child in cur.getList() or []:
                    q.append(child)

    return total
    
class NestedInteger:
    def __init__(self, value=None):
        # Store either an int OR a list of NestedInteger in one field.
        self._val = value if isinstance(value, int) else []

    def isInteger(self):
        return isinstance(self._val, int)

    def add(self, elem):
        # Ensure this holds a list, then append elem.
        if self.isInteger():
            self._val = []
        self._val.append(elem)

    def setInteger(self, value):
        self._val = value

    def getInteger(self):
        return self._val if self.isInteger() else None

    def getList(self):
        return self._val if not self.isInteger() else None


# ---------- Builders (kept) ----------

def build_nested(item):
    """
    Convert a Python nested structure (ints and lists) into NestedInteger objects.
    Example input: [7, [1, [2, 3]], 4]
    """
    if isinstance(item, int):
        return NestedInteger(item)

    ni = NestedInteger()
    for child in item:
        ni.add(build_nested(child))
    return ni


def build_nested_list(data):
    """
    Top-level builder: LeetCode provides a list[NestedInteger], not a single wrapper.
    """
    return [build_nested(x) for x in data]


# Driver code

def main():
    lists = [
        [1, [2, 3], 4],
        [[1, 1], 2, [1, [2, [1]]]],
        [[1, 2], [3, 4], [5, 6]],
        [1, [2, [3, [4, [5]]]]],
        [[[[[[1]]]]]]
    ]

    for i in range(len(lists)):
        nested_list = build_nested_list(lists[i])
        print(i + 1, ".\tNested list: ", lists[i], sep="")
        print("\tWeighted sum:", depthSum(nested_list))
        print("-" * 75)


if __name__ == "__main__":
    main()

Time Complexity

The time complexity of the solution is $O(N)$ because each nested element (integer or list) is added to the queue and processed at most once, and each list’s children are iterated exactly once when that list is expanded.

Space complexity

The space complexity of the solution is $O(W)$ because the queue stores the elements of the current and upcoming levels, where $W$ is the maximum number of items held in the queue at any time (the widest level); in the worst case, this becomes $O(N)$.

Interview Tips & Tricks

A few practical notes that tend to matter in interviews:

• Depth starts at level 1, not 0: This is the most common off-by-one mistake.
• Empty lists are valid: They contribute nothing but still appear in traversal.
• Negative integers are allowed: Don’t assume sums are non-negative.
• Recursion vs. iteration: Recursion is clean here, but an iterative BFS (using a queue with depth levels) is a good backup if a language has tight recursion limits.
• Mental model: Think of it as a tree where “going down one edge” increases depth by 111, and every integer node pays a “depth tax.”