# HashMap Java solution with Explanation

• HashMap solution

We have to find the maxDepth before we can do the sum calculation. So we use a HashMap to record the
integer we visited so far.

After we visited all inputs and got the maxDepth, we can start to calculate the sum.
In the HashMap we don't need to record all integers we visited, we just need to record the sum of integers
in current depth

Time complexity: O(N), N is num of inputs we have
Space complexity: O(H), H is maxDepth

`````` int maxDepth = 0;

public int depthSumInverse(List<NestedInteger> nestedList) {
//HashMap solution. We use HashMap to store nums in each depth before we find the maxDepth
//we will do the sum calculation in the last

HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>();

DFS( nestedList, 1, hs );

int sum = 0;

//get sum
for( int i = 1; i <= maxDepth; i++ ){
//put a checker here in case we dont have integer in one layer
if( hs.containsKey(i ) ) sum += hs.get(i) * (maxDepth + 1 -i);
}

return sum;
}

private void DFS(List<NestedInteger> nestedList, int depth,  HashMap<Integer, Integer> hs ){
//boundary check

if(nestedList.isEmpty()) return;

//update maxDepth if possible
maxDepth = Math.max(maxDepth, depth);

for( NestedInteger temp : nestedList ){
if( temp.isInteger() ){
//if temp is integer
if( !hs.containsKey(depth) ){
hs.put( depth, temp.getInteger()  );
}else{
hs.put( depth, hs.get(depth) + temp.getInteger()  );
}
}else{
//if temp is list
DFS(  temp.getList(), depth + 1, hs  );
}
}
}``````

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