Nested List Weight Sum II Solution in Java

Problem Description

Welcome to the whimsical world of nested lists! Imagine you’re at a family reunion, and everyone has brought their own dish. Some dishes are just a single item (like Aunt Edna’s famous potato salad), while others are a whole buffet of items (like Uncle Bob’s “everything but the kitchen sink” casserole). Your task is to calculate the “weight” of these dishes, but here’s the twist: the deeper the dish is nested, the less it counts!

In technical terms, you need to sum up the integers in a nested list, but you have to give less weight to integers that are deeper in the nesting. So, if you have a list like [1, [4, [6]]], the sum would be 1 + 4 + 6*1 = 11, where 6 is counted less because it’s deeper.

Code Solution


class Solution {
  public int depthSumInverse(List nestedList) {
    int ans = 0;
    int prevSum = 0;
    Queue q = new ArrayDeque<>(nestedList);

    while (!q.isEmpty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        final NestedInteger ni = q.poll();
        if (ni.isInteger())
          prevSum += ni.getInteger();
        else
          q.addAll(ni.getList());
      }
      ans += prevSum;
    }

    return ans;
  }
}

Approach

The approach used in the code is quite straightforward. We utilize a queue to traverse through the nested list level by level. For each level, we sum up the integers and keep track of the cumulative sum from the previous levels. This way, we can ensure that deeper integers contribute less to the final sum.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the total number of integers in the nested list. We visit each integer exactly once.
Space Complexity	O(D), where D is the maximum depth of the nested list. This is due to the queue storing the elements at each level.

Real-World Example

Think of it like a family tree. The grandparents (the top level) have the most influence, while the great-grandchildren (the deeper levels) have less. If you were to assign a “weight” to each family member based on their generation, you’d want to give more credit to the older generations. Similarly, in this problem, we give more weight to integers that are closer to the top of the nested structure.