Inverse-Depth Weighted Sum of a Nested Integer List

You are given a nested list of integers, written as a string in bracket notation such as "[3,[2,[5]]]". Each element of a list is either an integer or another list.

The depth of an integer is the number of lists that contain it, counting the outermost list. In "[3,[2,[5]]]", 3 has depth 1, 2 has depth 2 and 5 has depth 3. Let maxDepth be the largest depth of any integer in the input. The weight of an integer is maxDepth - depth + 1, so the most deeply nested integers have weight 1 and the integers directly inside the outermost list have the largest weight.

Return the sum, over every integer in the input, of the integer multiplied by its weight.

Function Signature

def inverse_depth_weighted_sum(nested: str) -> int:

Rules

• The string follows this grammar and contains no whitespace: a list is [, then zero or more elements separated by ,, then ]; an element is an integer or a list; an integer is an optional - followed by decimal digits, with no leading zeros other than the single digit 0 (so -0 never appears).
• The whole string is exactly one list, the outermost one.
• Only integers determine maxDepth. Empty lists, however deeply nested, contribute nothing and do not raise maxDepth.
• If the input contains no integers at all, for example "[]" or "[[],[[]]]", return 0.

Constraints

• 2 <= len(nested) <= 10^5
• nested is valid under the grammar above.
• Every integer is between -100 and 100 inclusive.
• Lists are nested at most 50 deep, counting the outermost list.
• Under these bounds the result fits in a signed 32-bit integer.

Examples

Example 1

• Input: nested = "[[2,2],3,[2,2]]"
• Output: 14
• Explanation: maxDepth is 2. The four 2s have depth 2 and weight 1, contributing 8; the 3 has depth 1 and weight 2, contributing 6.

Example 2

• Input: nested = "[3,[2,[5]]]"
• Output: 18
• Explanation: maxDepth is 3, so the weights of 3, 2 and 5 are 3, 2 and 1: 3*3 + 2*2 + 5*1 = 18.

Example 3

• Input: nested = "[2,[[]],[-1]]"
• Output: 3
• Explanation: The empty list inside [[]] holds no integer, so maxDepth is 2, not 3. The result is 2*2 + (-1)*1 = 3.

Bottom-Up Weighted Nested Sum

Hints

1. You never need to build the nested structure; a single left-to-right scan that tracks the current depth is enough to know each integer's depth.
2. The weight depends on maxDepth, which you only know at the end. Can you rewrite sum(v * (maxDepth - depth + 1)) as a combination of quantities you can accumulate without knowing maxDepth yet?
3. Update maxDepth only when you actually read an integer, so empty lists never affect it.

Approach

Scan the string once while keeping the current depth: '[' increments it, ']' decrements it, ',' is skipped, and any other character starts an integer token (optional '-', then digits) that is parsed in place. For every integer v at depth d we accumulate total += v and weighted += v * d, and raise maxDepth to d. Because sum(v * (maxDepth - d + 1)) = (maxDepth + 1) * sum(v) - sum(v * d), the answer is (maxDepth + 1) * total - weighted, which needs no second pass and no knowledge of maxDepth in advance. maxDepth is only updated when an integer is read, so empty lists never raise it, and an input with no integers leaves total = weighted = 0 and returns 0. With at most about 25,000 integers of magnitude 100 and depth at most 50, every intermediate stays well within 32-bit range.

• Time complexity: O(n) where n = len(nested)
• Space complexity: O(1) extra space