medium Nested List Weight Sum

Problem Statement

You are given a nestedList. Each element of the nestedList contains either integers or other such nested lists.

The depth level is determined by how many levels of nested lists the integer is within. For example, each element of the list [1, 1, [2], [2, [3]]] represents the depth of itself.

Return the sum of all integers of the list after multiplying each integer with its depth level.

Examples

• Example 1:

  • Input: [[2, [3, 4]], [5, 6], 7]
  • Expected Output: 54
  • Justification: The sum is calculated as 4 (2 at depth 2) + 9 (3 at depth 3) + 12 (4 at depth 3) + 10 (5 at depth 2) + 12 (6 at depth 2) + 7 (7 at depth 1).

• Example 2:

  • Input: [1, [4, [6]]]
  • Expected Output: 27
  • Justification: The sum is 1 (depth 1) + 8 (4 at depth 2) + 18 (6 at depth 3).

• Example 3:

  • Input: [5, [2, [3, [4]]], 1]
  • Expected Output: 35
  • Justification: The calculation is 5 (depth 1) + 4 (2 at depth 2) + 9 (3 at depth 3) + 16 (4 at depth 4) + 1 (depth 1).

Solution

To solve this problem, a recursive approach is ideal. This approach works by traversing each element in the list. If the element is an integer, we multiply it by its depth and add it to the total sum. If the element is another list, we recursively process this list, increasing the depth by one.

This method is effective because it naturally handles the nested structure of the input and ensures that each integer is multiplied by its correct depth level. The recursion elegantly simplifies the process of diving into nested lists and accumulating the weighted sum.

Step-by-Step Algorithm

• Define a method nestedSum which takes a nested list and an integer depth.
• Initialize a variable totalSum to 0.
• Iterate through each element in the nested list.
  • If the element is an integer, add it to totalSum multiplied by depth.
  • If the element is a list, recursively call nestedSum with the list and depth + 1, and add the result to totalSum.
• Return totalSum.

Algorithm Walkthrough

Let's consider the input: [[2, [3, 4]], [5, 6], 7].

1. Start with the outer list: [[2, [3, 4]], [5, 6], 7] with depth = 1.
2. The first element is [2, [3, 4]]. It's a nested list, so we process its elements:
   • 2 is an integer at depth = 2. Add 2 * 2 = 4 to totalSum.
   • [3, 4] is another nested list. Process its elements at depth = 3:
     • 3 is an integer. Add 3 * 3 = 9 to totalSum.
     • 4 is an integer. Add 4 * 3 = 12 to totalSum.
3. The second element is [5, 6], another list at depth = 2. Process its elements:
   • 5 is an integer. Add 5 * 2 = 10 to totalSum.
   • 6 is an integer. Add 6 * 2 = 12 to totalSum.
4. The third element is 7, a single integer at depth = 1. Add 7 * 1 = 7 to totalSum.
5. Summing all these, the total sum is 4 + 9 + 12 + 10 + 12 + 7 = 54.

Code

import java.util.ArrayList;
import java.util.List;

// NestedInteger class represents either a single integer or a nested list of integers
class NestedInteger {

  private Integer value;
  private List<NestedInteger> list;
  private boolean isSingleInteger;

  // Constructor for a single integer
  public NestedInteger(int value) {
    this.value = value;
    this.isSingleInteger = true;
  }

  // Constructor for an empty nested list
  public NestedInteger() {
    this.list = new ArrayList<>();
    this.isSingleInteger = false;
  }

  // Returns true if this NestedInteger holds a single integer
  public boolean isInteger() {
    return isSingleInteger;
  }

  // Returns the single integer that this NestedInteger holds, if it holds a single integer
  public Integer getInteger() {
    return isSingleInteger ? value : null;
  }

  // Adds a NestedInteger to this nested list
  public void add(NestedInteger ni) {
    if (!isSingleInteger) {
      this.list.add(ni);
    }
  }

  // Returns the nested list that this NestedInteger holds, if it holds a nested list
  public List<NestedInteger> getList() {
    return isSingleInteger ? new ArrayList<>() : list;
  }
}

// Solution class with a method to calculate the nested list weight sum
public class Solution {

  // Calculates the sum of integers in the nested list, weighted by their depth
  private int nestedSum(List<NestedInteger> nestedList, int depth) {
    int totalSum = 0;
    for (NestedInteger ni : nestedList) {
      if (ni.isInteger()) {
        // If it's a single integer, add its value multiplied by its depth
        totalSum += ni.getInteger() * depth;
      } else {
        // If it's a nested list, recursively calculate its sum
        totalSum += nestedSum(ni.getList(), depth + 1);
      }
    }
    return totalSum;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Modified Example 1: [[2, [3, 4]], [5, 6], 7]
    // Creating the nested list structure
    NestedInteger list1Sublist = new NestedInteger();
    list1Sublist.add(new NestedInteger(3));
    list1Sublist.add(new NestedInteger(4));

    NestedInteger list1 = new NestedInteger();
    list1.add(new NestedInteger(2));
    list1.add(list1Sublist);

    NestedInteger list2 = new NestedInteger();
    list2.add(new NestedInteger(5));
    list2.add(new NestedInteger(6));

    List<NestedInteger> modExample1 = new ArrayList<>();
    modExample1.add(list1);
    modExample1.add(list2);
    modExample1.add(new NestedInteger(7));

    // Calculating and printing the sum
    System.out.println("Output: " + solution.nestedSum(modExample1, 1));
  }
}

Complexity Analysis

• Time Complexity: O(N), where N is the total number of elements in the list, including nested lists. This is because each element is processed exactly once.
• Space Complexity: O(D), where D is the maximum depth of the nested lists. This is due to the recursive stack.