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.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Examples

Example 1:

Input: [ [1,1],2,[1,1] ]
Output: 8
Explanation: Four 1's at depth 1, one 2 at depth 2.
elements11211maxDepthSum of elements * depth
depths221222
weight112111x1+1x1+2x2+1x1+1x1 = 8

Example 2:

Input: [ 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.
elements146maxDepthSum of elements * depth
depths1233
weight3211x3 + 4x2 + 6x1 = 17

Solution

Method 1 - Recursion

Here are the steps:

  1. Calculate Maximum Depth:
    • Traverse the nested list to determine the maximum depth of any integer.
  2. Compute Weighted Sum:
    • Traverse the list again, and for each integer, compute the weighted sum by using the formula weight = maxDepth - (depth of the integer) + 1.

Code

Java

Here is NestedInteger interface:

// 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();
}

public class Solution {
    public int findMaxDepth(List<NestedInteger> nestedList) {
        int maxDepth = 1;
        for (NestedInteger ni : nestedList) {
            if (!ni.isInteger()) {
                maxDepth = Math.max(maxDepth, 1 + findMaxDepth(ni.getList()));
            }
        }
        return maxDepth;
    }

    public int weightedDepthSum(
        List<NestedInteger> nestedList, int depth, int maxDepth) {
        int total = 0;
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {
                total += ni.getInteger() * (maxDepth - depth + 1);
            } else {
                total += weightedDepthSum(ni.getList(), depth + 1, maxDepth);
            }
        }
        return total;
    }

    public int depthSumInverse(List<NestedInteger> nestedList) {
        int maxDepth = findMaxDepth(nestedList);
        return weightedDepthSum(nestedList, 1, maxDepth);
    }
}
Python

Here is NestedInteger class:

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 findMaxDepth(self, nestedList):
        maxDepth = 1
        for element in nestedList:
            if not element.isInteger():
                maxDepth = max(
                    maxDepth, 1 + self.findMaxDepth(element.getList())
                )
        return maxDepth

    def weightedDepthSum(self, nestedList, depth, maxDepth):
        total = 0
        for element in nestedList:
            if element.isInteger():
                total += element.getInteger() * (maxDepth - depth + 1)
            else:
                total += self.weightedDepthSum(
                    element.getList(), depth + 1, maxDepth
                )
        return total

    def depthSumInverse(self, nestedList):
        maxDepth = self.findMaxDepth(nestedList)
        return self.weightedDepthSum(nestedList, 1, maxDepth)

Complexity

  • Time: O(n), where n is the total number of nested integers and lists. Each element is visited a constant number of times in both findMaxDepth and weightedDepthSum.
  • Space: O(d), where d is the maximum depth of the nested list. This accounts for the space used by the recursion stack.