Nested List Weight Sum

Nested List Weight Sum is a small problem that hides a big idea. The interviewer wants to see if you can walk a structure that nests inside itself. Each number’s value depends on how deep it sits. So you must carry the depth with you as you go down. That is the whole test.

🎯 The Problem

You get a list where each item is either a plain number or another list. That inner list can hold more numbers or even more lists. We call this a nested list, which means a list that contains other lists inside it.

• Every number has a weight equal to its depth.
• Depth means how many lists you opened to reach it.
• A number at the top sits at depth 1. One list deeper is depth 2.
• Multiply each number by its depth, then add all of them up.

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

Explanation:
- The four 1's that sit inside inner lists are at depth 2.
- The single 2 sits at the top, at depth 1.
- Sum = (1*2) + (1*2) + (2*1) + (1*2) + (1*2) = 2 + 2 + 2 + 2 + 2 = 10

Here is the nesting drawn as a tree. The top list is depth 1. The inner lists push their numbers to depth 2. This first diagram shows the shape we walk.

So the deeper a number sits, the more it counts. The number 2 only counts once because it is at the top. Each 1 counts twice because it sits one list deeper.

🌊 Approach 1: BFS Level by Level (Alternative)

The idea in one line: walk the structure one level at a time with a queue, counting the depth as you go down.

The idea:

• Use a queue, which is a line where you add to the back and take from the front.
• Process the whole structure level by level, from the top down.
• The level number is the depth for every number on that level.

How it works:

• Put the top list’s items in the queue. Start depth at 1.
• Take one full level at a time.
• A plain number adds number * depth to the total.
• A list pushes its items to the back for the next level.
• After a level is done, raise the depth by one.

Why it is weak:

• It works, but it reads less cleanly than recursion.
• The queue can hold a whole level at once, so it uses more memory.
• You have to track the depth by hand instead of carrying it for free.

Here is the level-order BFS code:

from collections import deque


def depth_sum(nested_list):
    queue = deque((item, 1) for item in nested_list)
    total = 0

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

    return total

🐢 Approach 2: DFS Recursion Carrying Depth (Best)

The idea in one line: walk each branch all the way down, carrying the current depth into every call.

The idea:

• Recursion means a function that calls itself on a smaller piece.
• The smaller piece here is the inner list.
• Each step into a deeper list calls the same function with depth + 1.

How it works:

• Walk the list item by item.
• A plain number adds number * depth to a running total.
• A list calls the function again with depth + 1.
• The returned value flows back up and joins the total.

Why it is clean:

• This style is depth-first search, or DFS. You go down one branch fully, then the next.
• The depth rides along in each call for free.
• No queue to manage. The call stack does the tracking.

This second diagram shows the recursion in action. The function visits the top list, then dives into each inner list with a bigger depth, then returns the totals back up.

Steps to Solve

1. Write a helper function that takes a list and the current depth.
2. Start a running total at zero.
3. Walk through every item in the list.
4. If the item is a plain number, add number * depth to the total.
5. If the item is itself a list, call the helper on it with depth + 1, and add what it returns.
6. Return the total for this list.
7. Start the whole thing by calling the helper on the top list with depth 1.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int isInteger;       // 1 if this node is a plain number
    int value;           // used when isInteger is 1
    struct Node **list;  // used when isInteger is 0
    int size;            // how many children
} Node;

Node* makeInt(int v) {
    Node *n = malloc(sizeof(Node));
    n->isInteger = 1; n->value = v; n->list = NULL; n->size = 0;
    return n;
}

Node* makeList(Node **items, int size) {
    Node *n = malloc(sizeof(Node));
    n->isInteger = 0; n->value = 0; n->list = items; n->size = size;
    return n;
}

int dfs(Node *node, int depth) {
    if (node->isInteger) return node->value * depth;   // weight by depth
    int total = 0;
    for (int i = 0; i < node->size; i++) {
        total += dfs(node->list[i], depth + 1);        // go one level deeper
    }
    return total;
}

int main(void) {
    // build [[1, 1], 2, [1, 1]]
    Node *innerA[] = { makeInt(1), makeInt(1) };
    Node *innerB[] = { makeInt(1), makeInt(1) };
    Node *top[] = { makeList(innerA, 2), makeInt(2), makeList(innerB, 2) };
    Node *root = makeList(top, 3);
    printf("%d\n", dfs(root, 1));   // start at depth 1
    return 0;
}

10

#include <iostream>
#include <vector>
using namespace std;

struct NestedInteger {
    bool isInt;
    int value;
    vector<NestedInteger> list;
    NestedInteger(int v) : isInt(true), value(v) {}
    NestedInteger(vector<NestedInteger> l) : isInt(false), value(0), list(l) {}
};

int dfs(const NestedInteger& ni, int depth) {
    if (ni.isInt) return ni.value * depth;        // weight by depth
    int total = 0;
    for (const auto& child : ni.list) {
        total += dfs(child, depth + 1);           // go one level deeper
    }
    return total;
}

int main() {
    // build [[1, 1], 2, [1, 1]]
    NestedInteger innerA(vector<NestedInteger>{ NestedInteger(1), NestedInteger(1) });
    NestedInteger innerB(vector<NestedInteger>{ NestedInteger(1), NestedInteger(1) });
    NestedInteger root(vector<NestedInteger>{ innerA, NestedInteger(2), innerB });
    cout << dfs(root, 1) << endl;   // start at depth 1
    return 0;
}

10

import java.util.ArrayList;
import java.util.List;

public class NestedWeightSum {
    static class NestedInteger {
        boolean isInt;
        int value;
        List<NestedInteger> list = new ArrayList<>();
        NestedInteger(int v) { isInt = true; value = v; }
        NestedInteger(List<NestedInteger> l) { isInt = false; list = l; }
    }

    static int dfs(NestedInteger ni, int depth) {
        if (ni.isInt) return ni.value * depth;        // weight by depth
        int total = 0;
        for (NestedInteger child : ni.list) {
            total += dfs(child, depth + 1);           // go one level deeper
        }
        return total;
    }

    public static void main(String[] args) {
        List<NestedInteger> innerA = new ArrayList<>();
        innerA.add(new NestedInteger(1));
        innerA.add(new NestedInteger(1));
        List<NestedInteger> innerB = new ArrayList<>();
        innerB.add(new NestedInteger(1));
        innerB.add(new NestedInteger(1));
        List<NestedInteger> top = new ArrayList<>();
        top.add(new NestedInteger(innerA));
        top.add(new NestedInteger(2));
        top.add(new NestedInteger(innerB));
        NestedInteger root = new NestedInteger(top);
        System.out.println(dfs(root, 1));   // start at depth 1
    }
}

10

def dfs(nested, depth):
    total = 0
    for item in nested:
        if isinstance(item, list):        # item is a deeper list
            total += dfs(item, depth + 1) # go one level deeper
        else:                             # item is a plain number
            total += item * depth         # weight by depth
    return total


def depth_sum(nested):
    return dfs(nested, 1)                 # top level is depth 1


data = [[1, 1], 2, [1, 1]]
print(depth_sum(data))

10

function dfs(nested, depth) {
  let total = 0;
  for (const item of nested) {
    if (Array.isArray(item)) {       // item is a deeper list
      total += dfs(item, depth + 1); // go one level deeper
    } else {                         // item is a plain number
      total += item * depth;         // weight by depth
    }
  }
  return total;
}

function depthSum(nested) {
  return dfs(nested, 1); // top level is depth 1
}

const data = [[1, 1], 2, [1, 1]];
console.log(depthSum(data));

10

Let us read the Python version line by line, because the depth-carrying is the heart of it.

def dfs(nested, depth):
    total = 0

The helper takes the list it should walk and the depth that list sits at. We start a running total at zero for this list only. Each call has its own total.

    for item in nested:
        if isinstance(item, list):
            total += dfs(item, depth + 1)

We look at every item. isinstance(item, list) asks “is this item itself a list?” If yes, we step inside it. We call dfs again but with depth + 1, because everything in that inner list is one level deeper. The returned value flows back up and joins our total.

        else:
            total += item * depth

If the item is not a list, it is a plain number. We multiply it by the current depth and add it. This is where the weighting actually happens.

    return total

We hand this list’s total back to whoever called us. For the top call that whoever is depth_sum.

def depth_sum(nested):
    return dfs(nested, 1)

We kick the whole thing off at depth 1, because the top list is the shallowest level. From there the recursion handles every deeper level on its own. That clean start is why the helper needs the depth as a parameter.

⏱️ Time and Space Complexity

You visit every number and every list exactly once. So the time is O(n), where n is the total count of all items across all levels. The extra memory is the recursion itself. Each level of nesting adds one frame to the call stack. So the space is O(d), where d is the deepest level of nesting. A shallow list costs almost nothing. A very deep list costs more stack.

🧩 Key Takeaways

• ✅ Each number’s weight is its depth, so a deeper number counts for more.
• ✅ Walk the structure with depth-first search and carry the depth as a function parameter.
• ✅ When an item is a list, recurse into it with depth + 1.
• ✅ When an item is a number, add number * depth to the total.
• ✅ Time is O(n) over all items, and space is O(d), the deepest nesting level.

🚀 What’s Next?

• Nested List Weight Sum II
• Design Tic-Tac-Toe