Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Nested List Weight Sum II solution and explanation

MediumBreadth-First SearchDepth-First SearchStack6 min read66.8% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atLinkedInGoogleMeta
Practise Nested List Weight Sum II
9:19
Leetcode 364 - Nested List Weight Sum II (JAVA Solution Explained!)LC Bear · 9:19 · 3K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode 364 - Nested List Weight Sum II (JAVA Solution Explained!)LC Bear · 9:19 · 3K views
  2. Nested List Weight Sum II Leetcode Problem 364 Solution Linear Time || JavaScript codeSuperCode · 17:23 · 1K views
  3. LeetCode 364: Nested List Weight Sum IIKevin Dai · 3:55 · 930 views
  4. LeetCode Python 364 Nested List Weight Sum IINan Liu · 7:10 · 906 views
  5. Nested List Weight Sum II - 30 min Java Coding Challenge (Failed)Nihao, MrZhang · 36:55 · 699 views
  6. 364. Nested List Weight Sum II (Leetcode Medium)Programming Live with Larry · 8:50 · 438 views
  7. 364. Nested List Weight Sum II - Week 4/5 Leetcode November ChallengeProgramming Live with Larry · 8:21 · 431 views
  8. LeetCode 364 Nested List Weight Sum ii | THINKING OUT LOUD APPROACHNot a Competitive Coder · 16:04 · 250 views
  9. Leetcode 364. Nested List Weight Sum II (bfs)LetsCode · 6:18 · 175 views
  10. 364 Nested List Weight Sum II(Python & DFS & full walkthru)AlgBreaker · 4:04 · 169 views

The problem

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
1*3 + 4*2 + 6*1 = 17

Constraints:

  • 1 <= nestedList.length <= 50
  • 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.
  • There are no empty lists.

Approach overview

Problem Overview: You receive a nested list of integers where each element can either be a single integer or another list. The weight of each integer is determined by its depth from the bottom of the structure. Integers at the deepest level have weight 1, and the weight increases as you move toward the root. The task is to compute the total weighted sum.

Approach 1: Two-Pass DFS (O(n) time, O(d) space)

This method uses Depth-First Search to first determine the maximum depth of the nested structure. A recursive DFS walks through each element, increasing the depth when entering sublists. Once the maximum depth is known, run another DFS traversal and multiply each integer by (maxDepth - currentDepth + 1). Every element is visited twice, but the overall work remains linear. Space complexity is O(d) due to the recursion stack where d is the nesting depth.

Approach 2: BFS Level Accumulation (O(n) time, O(w) space)

A more elegant solution uses Breadth-First Search to process the structure level by level. Maintain two variables: unweighted (sum of all integers seen so far) and weighted (final result). During each level traversal, add integers to unweighted. After finishing the level, add unweighted to weighted. Because shallow integers persist across multiple levels, they effectively gain higher weights. This avoids computing maximum depth entirely while still visiting each element exactly once.

The BFS approach typically uses a queue to process lists iteratively. Each time you encounter a nested list, push its elements into the queue for the next level. This pattern is closely related to level-order traversal problems and sometimes appears with a Stack or queue depending on the implementation style.

Recommended for interviews: The BFS accumulation approach is usually the strongest answer. It solves the inverse-weight requirement without explicitly computing depth and keeps the runtime O(n) with clean logic. The two-pass DFS solution still demonstrates solid recursion and tree traversal skills, so mentioning it briefly shows broader understanding.

Solution

Let's assume the integers are a_1, a_2, cdots, a_n, their depths are d_1, d_2, cdots, d_n, the maximum depth is maxDepth, then the answer is:

$ a_1 times maxDepth - a_1 times d_1 + a_1 + a_2 times maxDepth - a_2 times d_2 + a_2 + cdots + a_n times maxDepth - a_n times d_n + a_n

which is:

(maxDepth + 1) times (a_1 + a_2 + cdots + a_n) - (a_1 times d_1 + a_2 times d_2 + cdots + a_n times d_n)

If we denote the sum of all integers as s, and the sum of each integer multiplied by its depth as ws, then the answer is:

(maxDepth + 1) times s - ws

Therefore, we design a function dfs(x, d), which starts searching from x with depth d. The execution process of dfs(x, d) is as follows:

  • We first update maxDepth = max(maxDepth, d);
  • If x is an integer, then we update s = s + x, ws = ws + x times d;
  • Otherwise, we recursively traverse each element y of x, and call dfs(y, d + 1).

We traverse the entire list, for each element x, we call dfs(x, 1), and finally return (maxDepth + 1) times s - ws.

The time complexity is O(n), and the space complexity is O(n). Where n$ is the number of integers.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        def dfs(x, d):
            nonlocal maxDepth, s, ws
            maxDepth = max(maxDepth, d)
            if x.isInteger():
                s += x.getInteger()
                ws += x.getInteger() * d
            else:
                for y in x.getList():
                    dfs(y, d + 1)

        maxDepth = s = ws = 0
        for x in nestedList:
            dfs(x, 1)
        return (maxDepth + 1) * s - ws
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    private int maxDepth;
    private int ws;
    private int s;

    public int depthSumInverse(List<NestedInteger> nestedList) {
        for (NestedInteger x : nestedList) {
            dfs(x, 1);
        }
        return (maxDepth + 1) * s - ws;
    }

    private void dfs(NestedInteger x, int d) {
        maxDepth = Math.max(maxDepth, d);
        if (x.isInteger()) {
            ws += x.getInteger() * d;
            s += x.getInteger();
        } else {
            for (NestedInteger y : x.getList()) {
                dfs(y, d + 1);
            }
        }
    }
}
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int maxDepth = 0, ws = 0, s = 0;
        function<void(NestedInteger&, int)> dfs = [&](NestedInteger& x, int d) {
            maxDepth = max(maxDepth, d);
            if (x.isInteger()) {
                ws += x.getInteger() * d;
                s += x.getInteger();
            } else {
                for (auto& y : x.getList()) {
                    dfs(y, d + 1);
                }
            }
        };
        for (auto& x : nestedList) {
            dfs(x, 1);
        }
        return (maxDepth + 1) * s - ws;
    }
};
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * function NestedInteger() {
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     @return {boolean}
 *     this.isInteger = function() {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     @return {integer}
 *     this.getInteger = function() {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     @return {void}
 *     this.setInteger = function(value) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     @return {void}
 *     this.add = function(elem) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds, if it holds a nested list
 *     Return null if this NestedInteger holds a single integer
 *     @return {NestedInteger[]}
 *     this.getList = function() {
 *         ...
 *     };
 * };
 */
/**
 * @param {NestedInteger[]} nestedList
 * @return {number}
 */
var depthSumInverse = function (nestedList) {
    let [maxDepth, ws, s] = [0, 0, 0];
    const dfs = (x, d) => {
        maxDepth = Math.max(maxDepth, d);
        if (x.isInteger()) {
            ws += x.getInteger() * d;
            s += x.getInteger();
        } else {
            for (const y of x.getList()) {
                dfs(y, d + 1);
            }
        }
    };
    for (const x of nestedList) {
        dfs(x, 1);
    }
    return (maxDepth + 1) * s - ws;
};
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     If value is provided, then it holds a single integer
 *     Otherwise it holds an empty nested list
 *     constructor(value?: number) {
 *         ...
 *     };
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     isInteger(): boolean {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     getInteger(): number | null {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     setInteger(value: number) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     add(elem: NestedInteger) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds,
 *     or an empty list if this NestedInteger holds a single integer
 *     getList(): NestedInteger[] {
 *         ...
 *     };
 * };
 */

function depthSumInverse(nestedList: NestedInteger[]): number {
    let [maxDepth, ws, s] = [0, 0, 0];
    const dfs = (x: NestedInteger, d: number) => {
        maxDepth = Math.max(maxDepth, d);
        if (x.isInteger()) {
            ws += x.getInteger() * d;
            s += x.getInteger();
        } else {
            for (const y of x.getList()) {
                dfs(y, d + 1);
            }
        }
    };
    for (const x of nestedList) {
        dfs(x, 1);
    }
    return (maxDepth + 1) * s - ws;
}
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */
func depthSumInverse(nestedList []*NestedInteger) int {
	var maxDepth, ws, s int
	var dfs func(*NestedInteger, int)
	dfs = func(x *NestedInteger, d int) {
		maxDepth = max(maxDepth, d)
		if x.IsInteger() {
			ws += x.GetInteger() * d
			s += x.GetInteger()
		} else {
			for _, y := range x.GetList() {
				dfs(y, d+1)
			}
		}
	}
	for _, x := range nestedList {
		dfs(x, 1)
	}
	return (maxDepth+1)*s - ws
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Two-Pass DFSO(n)O(d)When recursion is preferred and computing maximum depth first makes the logic clearer
BFS Level AccumulationO(n)O(w)Best general solution; processes levels iteratively without computing depth

Frequently asked questions

Is Nested List Weight Sum II easy or hard?

Nested List Weight Sum II is generally rated Medium difficulty. The challenge comes from recognizing that weights depend on distance from the bottom rather than the top. Once that insight is clear, a BFS accumulation or two-pass DFS approach solves the problem efficiently.

Nested List Weight Sum II Python/Java solution

The problem can be implemented in Python, Java, C++, Go, TypeScript, and JavaScript using DFS or BFS traversal. Python solutions typically use recursion for DFS or a deque for BFS. Java implementations often use a Queue for level traversal while accumulating weighted sums.

How to solve Nested List Weight Sum II in O(n)?

Traverse the nested list using BFS and maintain two variables: an unweighted running sum and a weighted result. At each level, add integers to the unweighted sum and then add that value to the weighted total. Because earlier integers are counted multiple times across levels, they receive larger weights automatically. Every element is processed once, giving O(n) time complexity.

What is the best approach for Nested List Weight Sum II?

The BFS level accumulation approach is usually considered the best solution. It processes the nested structure level by level while maintaining running sums of integers seen so far. Each level contributes the accumulated value again, which naturally applies inverse depth weights. The algorithm runs in O(n) time and avoids explicitly calculating the maximum depth.

Is Nested List Weight Sum II asked at Google/Amazon/Meta?

Nested list traversal and weighted sum variations frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The problem tests recursive thinking, BFS traversal, and handling hierarchical data structures. Interviewers often look for the optimized O(n) solution.

What data structure is used in Nested List Weight Sum II?

Common implementations use recursion with Depth-First Search or a queue for Breadth-First Search. DFS relies on the call stack to explore nested lists, while BFS uses a queue to process elements level by level. Both approaches handle hierarchical list structures efficiently.

What is the time complexity of Nested List Weight Sum II?

The optimal solutions run in O(n) time where n is the total number of integers and lists in the nested structure. Both DFS and BFS approaches visit every element exactly once. The space complexity depends on recursion depth for DFS or queue width for BFS.

Comments

Next problem · similarNested List Weight SumMedium
Now write it yourselfClose this page and solve Nested List Weight Sum II in the editor, without looking.
Practise Nested List Weight Sum II