Question

Formatted question description: https://leetcode.ca/all/364.html

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.

Algorithm

This question is an extension of the previous Nested List Weight Sum. The difference is that the deeper the depth, the smaller the weight, which is just the opposite of the previous one.

But the idea of solving the problem has not changed, you can still use DFS to do it, because you don’t know how deep the final depth is when traversing, you can directly accumulate the results when you can’t traverse.

The initial idea was to create a two-dimensional array during the traversal process, save the numbers of each layer, and finally know the depth, then calculate the weight sum.

But, to do it better, we can use two variables unweighted and weighted are used, the non-weighted sum and the weighted sum, which are initialized to 0.

If nestedList is not empty to start the loop, declare an empty array nextLevel first, traverse the elements in nestedList,
- If it is a number, then the non-weight sum plus this number,
- If it is an array, add nextLevel, After the traversal is completed, the number sum of the first level is stored in unweighted, and the rest of the elements are stored in nextLevel.

At this time, unweighted is added to weighted, and nextLevel is assigned to nestedList, so that it enters the next layer of calculation.

Since the value of the previous layer is still in unweighted, when the second layer is calculated and unweighted is added to weighted, it is equivalent to the sum of the numbers of the first layer being added twice, which perfectly meets the requirements.

Code

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

public class Nested_List_Weight_Sum_II {
    /**
     * // 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 null if this NestedInteger holds a single integer
     *     public List<NestedInteger> getList();
     * }
     */


    class Solution_onePass {

        public int depthSumInverse(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            int unweighted = 0, weighted = 0;
            while (!nestedList.isEmpty()) {

                List<NestedInteger> nextLevel = new ArrayList<>();

                for (NestedInteger a : nestedList) {
                    if (a.isInteger()) {
                        unweighted += a.getInteger();
                    } else {
                        nextLevel.add(nextLevel.size(), a); // append to rear
                    }
                }

                weighted += unweighted;
                nestedList = nextLevel;
            }

            return weighted;
        }
    }

    class Solution {
        private int maxDepth = 0;
        public int depthSumInverse(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            getDepth(1, nestedList);

            return depthSumHelper(maxDepth, nestedList);
        }

        private void getDepth(int level, List<NestedInteger> nestedList) {
            maxDepth = Math.max(maxDepth, level);
            for (NestedInteger n : nestedList) {
                if (!n.isInteger()) {
                    getDepth(level + 1, n.getList());
                }
            }
        }

        private int depthSumHelper(int depth, List<NestedInteger> nestedList) {
            int sum = 0;
            for (NestedInteger n : nestedList) {
                if (n.isInteger()) {
                    sum += depth * n.getInteger();
                } else {
                    sum += depthSumHelper(depth - 1, n.getList());
                }
            }

            return sum;
        }
    }

    // This is the interface that allows for creating nested lists.
    // You should not implement it, or speculate about its implementation
    private interface NestedInteger {

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

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }
}

############

/**
 * // 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) {
        int depth = maxDepth(nestedList);
        return dfs(nestedList, depth);
    }

    private int maxDepth(List<NestedInteger> nestedList) {
        int depth = 1;
        for (NestedInteger item : nestedList) {
            if (item.isInteger()) {
                continue;
            }
            depth = Math.max(depth, 1 + maxDepth(item.getList()));
        }
        return depth;
    }

    private int dfs(List<NestedInteger> nestedList, int depth) {
        int depthSum = 0;
        for (NestedInteger item : nestedList) {
            if (item.isInteger()) {
                depthSum += item.getInteger() * depth;
            } else {
                depthSum += dfs(item.getList(), depth - 1);
            }
        }
        return depthSum;
    }
}

// OJ: https://leetcode.com/problems/nested-list-weight-sum-ii/
// Time: O(N)
// Space: O(N)
class Solution {
private:
    int getDepth(vector<NestedInteger>& nestedList) {
        int ans = 0;
        for (auto &item : nestedList) ans = max(ans, item.isInteger() ? 0 : getDepth(item.getList()));
        return 1 + ans;
    }
    int getSum(vector<NestedInteger>& nestedList, int weight) {
        int sum = 0;
        for (auto &item : nestedList) sum += item.isInteger() ? (item.getInteger() * weight) : getSum(item.getList(), weight - 1);
        return sum;
    }
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int depth = getDepth(nestedList);
        return getSum(nestedList, depth);
    }
};

# """
# 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 max_depth(nestedList):
            depth = 1
            for item in nestedList:
                if item.isInteger():
                    continue
                depth = max(depth, max_depth(item.getList()) + 1)
            return depth

        def dfs(nestedList, max_depth):
            depth_sum = 0
            for item in nestedList:
                if item.isInteger():
                    depth_sum += item.getInteger() * max_depth
                else:
                    depth_sum += dfs(item.getList(), max_depth - 1)
            return depth_sum

        depth = max_depth(nestedList)
        return dfs(nestedList, depth)


class Solution_onePass: # iterative
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        if not nestedList: # can remove this check, an empty list in Python is considered "falsy" and the loop will exit when it reaches the end of the list
            return 0
        unweighted = weighted = 0
        while nestedList:
            next_level = []
            for a in nestedList:
                if a.isInteger():
                    unweighted += a.getInteger()
                else:
                    next_level.extend(a.getList())
            weighted += unweighted
            nestedList = next_level
        return weighted

############


class Solution(object):
  def depthSumInverse(self, nestedList):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """

    def getDepth(root):
      res = 0
      for nested in root:
        if not nested.isInteger():
          res = max(res, getDepth(nested.getList()))
      return res + 1

    def helper(root, depth, maxDepth):
      res = 0
      for nested in root:
        if nested.isInteger():
          res += (maxDepth - depth) * nested.getInteger()
        else:
          res += helper(nested.getList(), depth + 1, maxDepth)
      return res

    return helper(nestedList, 0, getDepth(nestedList))

/**
 * // 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) {
    const maxDepth = nestedList => {
        let depth = 1;
        for (const item of nestedList) {
            if (item.isInteger()) {
                continue;
            }
            depth = Math.max(depth, 1 + maxDepth(item.getList()));
        }
        return depth;
    };
    const dfs = (nestedList, depth) => {
        let depthSum = 0;
        for (const item of nestedList) {
            if (item.isInteger()) {
                depthSum += item.getInteger() * depth;
            } else {
                depthSum += dfs(item.getList(), depth - 1);
            }
        }
        return depthSum;
    };
    const depth = maxDepth(nestedList);
    return dfs(nestedList, depth);
};

364 - Nested List Weight Sum II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions