Skip to main content

364. Nested List Weight Sum II

mediumAsked at LinkedIn

Same as Nested List Weight Sum but the weighting is INVERTED — deepest leaves are weight 1 and the root is the heaviest. LinkedIn asks this as the trickier follow-up; the clean solution is a 'cumulative sum at each depth' trick that avoids two passes.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn onsite reports list II as a frequent follow-up after Nested List Weight Sum I.
  • Blind (2025-11)— LinkedIn writeups specifically describe the 'unweighted accumulator' trick as the signal.

Problem

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. The depth of an integer is the number of lists that it is inside of. Let maxDepth be the maximum depth of any integer. The weight of an integer is maxDepth - (the depth of the integer) + 1. Return the sum of each integer in nestedList multiplied by its weight.

Constraints

  • 1 <= nestedList.length <= 50
  • The values of the integers in the nested list is in the range [-100, 100].
  • The maximum depth of any integer is less than or equal to 50.

Examples

Example 1

Input
nestedList = [[1,1],2,[1,1]]
Output
8

Explanation: Four 1's at depth 2 with weight 1, one 2 at depth 1 with weight 2. 4 * 1 * 1 + 1 * 2 * 2 = 8.

Example 2

Input
nestedList = [1,[4,[6]]]
Output
17

Explanation: 1 at depth 1 -> weight 3; 4 at depth 2 -> weight 2; 6 at depth 3 -> weight 1. 1*3 + 4*2 + 6*1 = 17.

Approaches

1. Two-pass: find max depth then weighted sum

First DFS to find max depth. Second DFS computes value * (maxDepth - depth + 1) for each integer.

Time
O(N) total over two passes
Space
O(D) recursion
function depthSumInverseTwoPass(nestedList) {
  function maxDepth(list, depth) {
    let m = depth;
    for (const item of list) {
      if (!item.isInteger()) m = Math.max(m, maxDepth(item.getList(), depth + 1));
    }
    return m;
  }
  const max = maxDepth(nestedList, 1);
  function sum(list, depth) {
    let s = 0;
    for (const item of list) {
      if (item.isInteger()) s += item.getInteger() * (max - depth + 1);
      else s += sum(item.getList(), depth + 1);
    }
    return s;
  }
  return sum(nestedList, 1);
}

Tradeoff: Clear and direct. Two traversals but both are O(N). The main downside: you need to know maxDepth before weighting, so this doesn't work for streaming.

2. Single-pass with cumulative unweighted sum (optimal)

Walk BFS level by level. Maintain unweighted = sum of all integers seen so far. Total += unweighted at each level. The deepest integers contribute once; shallower ones contribute multiple times.

Time
O(N)
Space
O(N) queue
function depthSumInverse(nestedList) {
  let unweighted = 0, total = 0;
  let queue = nestedList.slice();
  while (queue.length) {
    const next = [];
    for (const item of queue) {
      if (item.isInteger()) unweighted += item.getInteger();
      else next.push(...item.getList());
    }
    total += unweighted;
    queue = next;
  }
  return total;
}

Tradeoff: Single-pass and elegant. Why it works: an integer at depth d gets counted in unweighted at level d, then at d+1, ..., up to maxDepth. That's (maxDepth - d + 1) contributions — exactly its weight.

LinkedIn-specific tips

LinkedIn interviewers grade whether you spot the single-pass insight. Articulate: 'An integer's weight equals the number of LEVELS BELOW or AT its depth. If I keep a running sum of values seen so far, adding it to the total at every level, each integer gets counted (max_depth - depth + 1) times — which is exactly its weight.' That's the entire solution.

Common mistakes

  • Trying to weight integers explicitly with the depth — works (two-pass) but misses the elegant single-pass.
  • In the single-pass version, resetting unweighted between levels — destroys the cumulative property.
  • Putting `total += unweighted` BEFORE adding the level's integers — off-by-one in the contribution count.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

  • What if the nesting were a DAG (with shared subtrees)? (Hash by identity to avoid double-counting.)
  • What if you needed to support online additions of integers? (Maintain per-depth sums in a map.)
  • Could you do this with the iterator interface from LC 341?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does the single-pass version work?

Because adding the running 'unweighted sum so far' to the total at each level effectively re-adds every integer once per level remaining below it. An integer at depth d is in the unweighted sum starting at level d and stays there through level maxDepth — exactly maxDepth - d + 1 levels, which is its weight.

Which version do interviewers prefer?

Most LinkedIn interviewers slightly prefer the single-pass version because it shows you saw the cumulative-sum trick. The two-pass version is acceptable but more mechanical.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Nested List Weight Sum II and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →