Nested List Weight Sum II LeetCode Solution

Difficulty Level Medium
Frequently asked in Facebook LinkedInViews 2430

Problem Statement

Nested List Weight Sum II LeetCode Solution – 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

Test Case 1:

Input:

nestedList = [[1, 1], 2, [1, 1]]

Output:

8

Nested List Weight Sum II LeetCode Solution

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

Approach:

We have to find the max depth before we can do the sum calculation. So we use a HashMap to record the integers we visited so far.

After we visited all inputs and got the maxDepth, we can start to calculate the sum.
In the HashMap we don’t need to record all integers we visited, we just need to record the sum of integers in current depth.

Two-Pass Solution

  • In the first pass, get the maximum depth of the nested list. The recursion is obvious – traverse the list and if there is any nestedList, find its depth. The final depth is the maximum depth from any nestedList.

Single Pass Solution with Cache

  • Engineer the solution like Nested List Weight Sum I, but store the sum at each level without any weights.
  • Once completed, you will know the maximum level which will be the depth. Use that to do the computation for the weighted sum.

Single Pass Solution using a BFS like approach

  • Add all the integers at a level to level_sum. Push all elements which are not an integer (and are list type) into the list for the next iteration. Make sure to flatten this list otherwise infinite loop.
  • Now we only initialize level_sum once. And successive level’s integers are added to it. Once a level finishes, we add it to total_sum. This naturally implements the multiplication logic – lower level sums are added multiple times to the total sum.

Code for Nested List Weight Sum II

Python Program

class Solution(object):
    def depthSumInverse(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        total_sum, level_sum = 0, 0
        while len(nestedList):
            next_level_list = []
            for x in nestedList:
                if x.isInteger():
                    level_sum += x.getInteger()
                else:
                    for y in x.getList():
                        next_level_list.append(y)
            total_sum += level_sum
            nestedList = next_level_list
        return total_sum

Java Program

/**
 * // 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 {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null) return 0;
        Queue<NestedInteger> queue = new LinkedList<NestedInteger>();
        int prev = 0;
        int total = 0;
        for (NestedInteger next: nestedList) {
            queue.offer(next);
        }
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                NestedInteger current = queue.poll();
                if (current.isInteger()) levelSum += current.getInteger();
                List<NestedInteger> nextList = current.getList();
                if (nextList != null) {
                    for (NestedInteger next: nextList) {
                        queue.offer(next);
                    }
                }
            }
            prev += levelSum;
            total += prev;
        }
        return total;
    }
}

Complexity Analysis for Nested List Weight Sum II LeetCode Solution

Time Complexity: Each nested element is put in the queue and removed from the queue exactly once.

Space Complexity: O(N). The worst-case for space complexity in BFS occurs when the majority of elements are at the same depth.

Translate »