No depth variable, no multiplication


  • 165

    Inspired by lzb700m's solution and one of mine. Instead of multiplying by depth, add integers multiple times (by going level by level and adding the unweighted sum to the weighted sum after each level).

    public int depthSumInverse(List<NestedInteger> nestedList) {
        int unweighted = 0, weighted = 0;
        while (!nestedList.isEmpty()) {
            List<NestedInteger> nextLevel = new ArrayList<>();
            for (NestedInteger ni : nestedList) {
                if (ni.isInteger())
                    unweighted += ni.getInteger();
                else
                    nextLevel.addAll(ni.getList());
            }
            weighted += unweighted;
            nestedList = nextLevel;
        }
        return weighted;
    }

  • 2
    L

    Great catch using weighted and unweighted trick! Better than the recursive solution.


  • 0

    Wrong answer with the test case of [1,[4,[6,[[[]]] ] ]]


  • 0

    Not necessarily. The problem is ambiguous there, and my solution passes all tests of the test suite.


  • 0
    G

    Awesome idea!


  • 0
    D

    brilliant... And out of curiosity, if we were to solve this iteratively using DFS, is anyway to do it without first looking for the max depth?


  • 0

    @dianhua1560 Not yet answering your question, but: Why would you want to use DFS iteratively rather than recursively?


  • 0
    D

    @StefanPochmann I guess it's because I find iterative solutions more helpful while practicing, and I feel like I already know how to do this recursively.


  • 0
    W

    @StefanPochmann said in No depth variable, no multiplication:

    int unweighted = 0, weighted = 0;
    while (!nestedList.isEmpty()) {
        List<NestedInteger> nextLevel = new ArrayList<>();
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger())
                unweighted += ni.getInteger();
            else
                nextLevel.addAll(ni.getList());
        }
        weighted += unweighted;
        nestedList = nextLevel;
    }
    return weighted;
    

    accepted!!!!!!


  • 0
    C

    @StefanPochmann How did you come up with this kind of idea? Is it also some known tricks to people interested in coding puzzles? Thanks


  • 0
    L

    Elegant solution!


  • 1
    T

    Is it possible to do the same thing in Python? I didn't see the constructor function in NestedList so I'm not sure if the creation of an empty object works


  • 0
    H

    If I understand it right, every "true" number will be accessed twice. Once when it is added to the sum, the other time when construct the level this number is in. So this shouldn't be too much faster than the 2-pass algorithm?


  • 0
    E

    Elegant solution!


  • 0
    J

    @StefanPochmann Hi Stefan, is this algo O(N) time complexity (totally N integers in all levels) and O(max(N, depth)) space complexity?
    Thanks! : )


  • 0
    R

    great algorithm!


  • 0
    R

    really nice solution. I love you.


  • 0
    L

    when I rewrite this algorithm in Python, I came across problem like:
    Line 54: AttributeError: 'generator' object has no attribute 'isInteger' in "for item in nestedList:" Anyone help me figure it out?

    the code is attached below:

    def depthSumInverse(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        weighted, unweighted = 0, 0
        while len(nestedList) != 0:
            nextLevel = []
            for item in nestedList:
                if item.isInteger():
                    unweighted += item.getInteger()
                else:
                    nextLevel.append(i for i in item.getList())
                
            weighted += unweighted
            nestedList = nextLevel
            
        return weighted

  • 1
    C

    @leiyama001 same problem here for my iterative solution: AttributeError: 'list' object has no attribute 'getInteger'. looks like python treat a nested list as a python-defined list?

    but OK for my recursive solution, not sure why?

    iterative solution:

        def depthSumInverse(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            unweighted, weighted = 0, 0
            while nestedList:
                nextlevel = []
                for item in nestedList:
                    if item.isInteger():
                        unweighted += item.getInteger()
                    else:
                        nextlevel.append(item.getList())
                weighted += unweighted
                nestedList = nextlevel
            return weighted
    

    recursive solution using dict

        def depthSumInverse(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            ret = collections.defaultdict(int)
            self.helper(nestedList, 1, ret)
            if not ret:
                return 0
            depth = max(ret.keys())
            retsum = 0
            for k, v in ret.items():
                retsum += (depth-k+1) * v
            return retsum
            
        def helper(self, lists, i, path):
            if not lists: return
            for item in lists:
                if item.isInteger():
                    path[i] += item.getInteger()
                else:
                    self.helper(item.getList(), i+1, path)

  • 0
    S

    @leiyama001

    nextLevel.append(i for i in item.getList())
    

    Instead of appending a list, you should extend it. This should work:

    class Solution(object):
        def depthSumInverse(self, nestedList):
            """
            :type nestedList: List[NestedInteger]
            :rtype: int
            """
            weighted, unweighted = 0, 0
            while nestedList:
                nextLevel = []
                for item in nestedList:
                    if item.isInteger():
                        unweighted += item.getInteger()
                    else:
                        nextLevel += item.getList()
                weighted += unweighted
                nestedList = nextLevel
            return weighted

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.