One pass, without hashmap


  • 0
    Y

    Some suggested to use two passes - first one for getting the max depth;
    Others suggested to use one pass, but with a hashmap to store numbers for each depth.

    This is a one pass solution without a hashmap/vector.
    When we encounter an element in the list, we don't know its depth to multiply, but we can assume
    the depth for the root of the tree is "d", so given example [1,[2,[3]]], we have:
    1 * d + 2 * (d-1) + 3 * (d-2) = 6*d - 8 (let's denote this as "x * d + y")

    public class Solution {
        public int depthSumInverse(List<NestedInteger> nestedList) {
            int[] res = new int[2]; // store [x, y] mentioned above
            int depth = helper(nestedList, res, 0);
            return res[0] * depth - res[1]; // use long if overflows, but it's fine with the current test cases
        }
        
        private int helper(List<NestedInteger> nestedList, int[] res, int depth) {
            int sum = 0;
            int max = 1;
            for (NestedInteger item : nestedList) {
                if (item.isInteger()) {
                    sum += item.getInteger();
                } else {
                    max = Math.max(max, helper(item.getList(), res, depth+1) + 1);
                }
            }
            res[0] += sum;
            res[1] += sum * depth;
            return max;
        }
    }
    

Log in to reply
 

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