Nested List Weight Sum

Nested List Weight Sum is a classic Meta (Facebook) interview problem involving a nested list of integers and sublists. Each integer contributes to the total sum based on its depth (multiplied by its nesting level), solvable via DFS recursion, BFS level-order traversal, or iterative stack approaches.[1][3][7]

Problem Statement

Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Depth starts at 1 for the outermost level and increases by 1 for each nested level. Each NestedInteger can be either an integer or a list of NestedIntegers.[3][8][1]

Key Examples

The standard example input is [[1,1],2,[1,1]]:

• Depth 1: 2 → contributes 2 * 1 = 2
• Depth 2: four 1s → each contributes 1 * 2 = 2 (total 8)
• Expected output: 10[5][3]

Another common example is [1,[4,[6]]]:

• Depth 1: 1 → 1 * 1 = 1
• Depth 2: 4 → 4 * 2 = 8
• Depth 3: 6 → 6 * 3 = 18
• Expected output: 27[9]

For [1,[2,2],[[3],2],1]:

• Depth 1: first 1 and last 1 → 1*1 + 1*1 = 2
• Depth 2: two 2s → 2*2 + 2*2 = 8
• Depth 3: 3 → 3*3 = 9
• Expected output: 19 (adjusted from some sources showing depth-multiplied sums).[8]

Constraints

• 1 <= nestedList.length <= 50
• Integers are in range [-100, 100]
• Nesting depth up to 50 levels (safe for recursion stack)
• List can be empty at any level (contributes 0 but counts for depth)
• Input follows NestedInteger interface: isInteger(), getInteger(), getList()[2][1][3]