_339. Nested List Weight Sum.md

339. Nested List Weight Sum

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 : Depth-First Search, Breadth-First Search

Acceptance Rate : 84.27 %

---

Solutions

• m339.c
• m339.py

C

m339.c

/**
 * *********************************************************************
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * *********************************************************************
 *
 * // Initializes an empty nested list and return a reference to the nested integer.
 * struct NestedInteger *NestedIntegerInit();
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * bool NestedIntegerIsInteger(struct NestedInteger *);
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * int NestedIntegerGetInteger(struct NestedInteger *);
 *
 * // Set this NestedInteger to hold a single integer.
 * void NestedIntegerSetInteger(struct NestedInteger *ni, int value);
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 * void NestedIntegerAdd(struct NestedInteger *ni, struct NestedInteger *elem);
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * struct NestedInteger **NestedIntegerGetList(struct NestedInteger *);
 *
 * // Return the nested list's size that this NestedInteger holds, if it holds a nested list
 * // The result is undefined if this NestedInteger holds a single integer
 * int NestedIntegerGetListSize(struct NestedInteger *);
 * };
 */
int helper(struct NestedInteger* curr, int multiplier) {
    if (NestedIntegerIsInteger(curr)) {
        return multiplier * NestedIntegerGetInteger(curr);
    }
    
    int lstSize = NestedIntegerGetListSize(curr);
    struct NestedInteger** lst = NestedIntegerGetList(curr);
    
    int output = 0;
    for (int i = 0; i < lstSize; i++) {
        output += helper(lst[i], multiplier + 1);
    }

    return output;
}

int depthSum(struct NestedInteger** nestedList, int nestedListSize) {
    int output = 0;
    for (int i = 0; i < nestedListSize; i++) {
        output += helper(nestedList[i], 1);
    }
    return output;
}

Python

m339.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 depthSum(self, nestedList: List[NestedInteger]) -> int:
        def helper(multiplier: int, curr: NestedInteger) -> int :
            if curr.isInteger() :
                return multiplier * curr.getInteger()

            output = 0
            for i in curr.getList() :
                output += helper(multiplier + 1, i)
            return output

        return sum([helper(1, x) for x in nestedList])