_364. Nested List Weight Sum II.md

364. Nested List Weight Sum II

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 02, 2024

Last updated : July 02, 2024

---

Related Topics : Stack, Depth-First Search, Breadth-First Search

Acceptance Rate : 64.66 %

---

Solutions

• m364.java
• m364.py

Java

m364.java

/**
 * // 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 maxx = 1;
        int output = 0;

        Stack<Pair<Integer, Integer>> valsAndDepth = new Stack<>();
        Stack<Pair<NestedInteger, Integer>> toVisit = new Stack<>();
        
        for (NestedInteger i : nestedList)
            toVisit.add(new Pair(i, 1));
        
        while (!toVisit.isEmpty()){
            Pair<NestedInteger, Integer> curr = toVisit.pop();

            maxx = Integer.max(maxx, curr.getValue());
            if (curr.getKey().isInteger()) {
                valsAndDepth.push(new Pair(curr.getKey().getInteger(), curr.getValue()));
                continue;
            }

            for (NestedInteger i : curr.getKey().getList())
                toVisit.add(new Pair(i, curr.getValue() + 1));
        }

        while (!valsAndDepth.isEmpty()) {
            Pair<Integer, Integer> curr = valsAndDepth.pop();
            output += curr.getKey() * (maxx - curr.getValue() + 1);
        }

        return output;
    }
}

Python

m364.py

# """
# 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:
        maxx = 1
        output = 0

        valsAndDepth = []
        toVisit = [(x, 1) for x in nestedList]

        while toVisit :
            curr, depth = toVisit.pop()
            maxx = max(maxx, depth)
            if curr.isInteger() :
                valsAndDepth.append((curr.getInteger(), depth))
                continue

            for x in curr.getList() :
                toVisit.append((x, depth + 1))

        output = 0
        while valsAndDepth :
            val, depth = valsAndDepth.pop()
            output += val * (maxx - depth + 1)

        return output