304. Nested List Weight Sum II
You receive nested, a nested list of integers: each element is either an integer or another list of the same kind (in Python it arrives as a plain nested list; in C++/Java each element is a NestedItem with an isInt flag, a val field, and an items child list).
An integer sitting directly in the outer list has depth 1; wrapping it in one more list adds 1 to its depth. Let maxDepth be the depth of the deepest integer anywhere in the structure. Each integer's weight is flipped relative to the usual convention: an integer at depth d weighs maxDepth - d + 1, so the shallowest integers count the most and the deepest count exactly once.
Return the sum of every integer multiplied by its weight.
Example 1:
Input: nested = [[1, 1], 2, [1, 1]]
Output: 8
Explanation: maxDepth is 2. The four 1s sit at depth 2, so each weighs 2 − 2 + 1 = 1; the 2 sits at depth 1 and weighs 2. Total: 4·(1·1) + 1·(2·2) = 8.
Example 2:
Input: nested = [1, [4, [6]]]
Output: 17
Explanation: maxDepth is 3. The 1 (depth 1) weighs 3, the 4 (depth 2) weighs 2, the 6 (depth 3) weighs 1: 1·3 + 4·2 + 6·1 = 17.
Constraints:
- 1 ≤ total number of integers ≤ 10⁴
- -100 ≤ each integer ≤ 100
- The nesting depth is at most 50.
- No list in the input is empty, so maxDepth is well defined.
Hints:
The weight of an integer depends on maxDepth, which you don't know until you have seen the whole structure. The most direct fix: one traversal to measure maxDepth, a second traversal to add up value × (maxDepth − depth + 1).
You can avoid knowing maxDepth entirely. Walk the structure level by level and keep a running sum of all integers seen so far; add that running sum to the total once per level. An integer first counted at depth d gets re-added on every deeper level — exactly maxDepth − d + 1 times.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nested = [[1, 1], 2, [1, 1]]
Expected output: 8