2ms easy to understand java solution


  • 38
    L
    public int depthSum(List<NestedInteger> nestedList) {
        return helper(nestedList, 1);
    }
    
    private int helper(List<NestedInteger> list, int depth)
    {
        int ret = 0;
        for (NestedInteger e: list)
        {
            ret += e.isInteger()? e.getInteger() * depth: helper(e.getList(), depth + 1);
        }
        return ret;
    }

  • 1
    B

    what do you think the time complexity of your solution? I was wondering which is the best one, BFS or naive. Thanks.


  • 3
    L

    do not know what you meant by naive. The time complexity of my solution is O(n), n is the number of elements or Integer within the list.


  • 1
    S

    yes, also the space complexity would be O(k) where k is the max level of depth.


  • 6
    T

    @larrywang2014 Same idea but better readability.

    public class Solution {
        public int depthSum(List<NestedInteger> nestedList) {
            return depthSum(nestedList, 1);
        }
        public int depthSum(List<NestedInteger> nestedList, int level) {
            int result = 0;
            for(NestedInteger ni : nestedList) {
                if (ni.isInteger()) {
                    result = result + (level * ni.getInteger());
                }else {
                    result = result + depthSum(ni.getList(), level+1);
                }
            }
            return result;
        }
    

    }


  • 1

    Depth sum using stack.

        public int depthSum(List<NestedInteger> nestedList) {
            int res = 0;
            Stack<Iterator<NestedInteger>> stk = new Stack<>();
            stk.push (nestedList.iterator());
            
            while (!stk.isEmpty()) {
                Iterator<NestedInteger> itr = stk.peek ();
                while (itr.hasNext()) {
                    NestedInteger n = itr.next();
                    if (n.isInteger()) res += n.getInteger() * stk.size ();
                    else {
                        stk.push (n.getList().iterator());
                        break;
                    }
                }
                if (!stk.peek ().hasNext()) stk.pop ();
            }
            return res;
        }
    

Log in to reply
 

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