Question

Formatted question description: https://leetcode.ca/all/339.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.

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

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.

Example 2:

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

Example 3:

Input: nestedList = [0]
Output: 0

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

Traverse the given nested linked list array, for each nested linked list object, call the dfs function, assign a depth value of 1, and add up and return. In the dfs function, first determine whether it is an integer,

If yes, it returns the current depth multiplied by an integer
If not, then we traverse the nested array again, call the recursive function for each nested linked list, and add up the return value to return

Code

import java.util.List;

public class Nested_List_Weight_Sum {
    /**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * public 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();
     * }
     */
    public class Solution_dfs {
        public int depthSum(List<NestedInteger> nestedList) {
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }

            return depthSumHelper(nestedList, 1);
        }

        private int depthSumHelper(List<NestedInteger> list, int depth) {
            if (list.isEmpty()) {
                return 0;
            }

            int sum = 0;

            for (NestedInteger curr: list){
                // for each in list, perform a dfs
                if (curr.isInteger()) {
                    sum += curr.getInteger() * depth;
                } else {
                    sum += depthSumHelper(curr.getList(), depth + 1);
                }
            }

            return sum;
        }
    }

    public class Solution_stack {

        /*
            用一个stack来实现。
            遍历list，将当前元素和深度加入stack中。
            依次取出栈顶元素，
                若取出元素为数，则将其乘以其深度并加入sum，
                若取出元素是list，则将该list中元素依次加入stack中，同时这些元素的深度比之前取出元素深度＋1
         */
        class Node {
            int depth;
            NestedInteger nestedInteger;

            public Node(int depth, NestedInteger nestedInteger) {
                this.depth = depth;
                this.nestedInteger = nestedInteger;
            }
        }

        public int depthSum(List<NestedInteger> nestedList) {

            Stack<Node> stack = new Stack<Node>();
            for (int i = 0; i < nestedList.size(); i++) {
                stack.push(new Node(1, nestedList.get(i)));
            }

            int sum = 0;
            while (!stack.isEmpty()) {
                Node current = stack.pop();
                if (current.nestedInteger.isInteger()) {
                    sum += current.depth * current.nestedInteger.getInteger();
                } else {
                    List<NestedInteger> list = current.nestedInteger.getList();
                    for (int i = 0; i < list.size(); i++) {
                        stack.push(new Node(current.depth + 1, list.get(i)));
                    }
                }
            }

            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 depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }

    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/
// Time: O(N)
// Space: O(D) where D is the max depth of the list.
class Solution {
private:
    int depthSum(vector<NestedInteger>& nestedList, int depth) {
        int sum = 0;
        for (auto &i : nestedList) {
            if (i.isInteger()) sum += i.getInteger() * depth;
            else sum += depthSum(i.getList(), depth + 1);
        }
        return sum;
    }
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return depthSum(nestedList, 1);
    }
};

# """
# 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 depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nestedList, depth):
            depth_sum = 0
            for item in nestedList:
                if item.isInteger():
                    depth_sum += item.getInteger() * depth
                else:
                    depth_sum += dfs(item.getList(), depth + 1)
            return depth_sum

        return dfs(nestedList, 1)


class Solution: # iterative
    def depthSum(self, nestedList):
        stack = []
        for nestedInteger in nestedList:
            stack.append((1, nestedInteger))

        ans = 0
        while stack:
            depth, current = stack.pop()
            if current.isInteger():
                ans += depth * current.getInteger()
            else:
                lst = current.getList()
                for nestedInteger in lst:
                    stack.append((depth+1, nestedInteger))

        return ans


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

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    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(object):
  def depthSum(self, nestedList):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """

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

    return helper(nestedList, 1)

/**
 * // 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 depthSum = function (nestedList) {
    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;
    };
    return dfs(nestedList, 1);
};

339 - Nested List Weight Sum

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions