1036. Inverse Depth Total
A shipping manifest items nests crates inside containers, and containers inside bigger containers. Each entry is either an integer (a crate with a declared value) or a list of more entries. Entries directly inside items have depth 1; anything inside a container at depth d has depth d + 1.
This time deeper crates are the ones that get priority. Let D be the depth of the deepest integer anywhere in items. A crate at depth d has weight D - d + 1, so the deepest crates weigh 1 and top-level crates weigh the most. Return the sum of value times weight over all crates. If there are no integers at all, return 0. Empty containers do not influence D.
Target O(n) time and O(d) extra space.
Example 1
- Input:
- items = [3,[2,[5]],4]
- Output:
- 30
- Explanation:
The deepest integer (5) is at depth 3, so weights are 3, 2, 1, 3 and the total is 9 + 4 + 5 + 12 = 30.
Example 2
- Input:
- items = [[[-2]],7]
- Output:
- 19
- Explanation:
D is 3, so -2 at depth 3 has weight 1 and 7 at depth 1 has weight 3, giving -2 + 21 = 19.
Example 3
- Input:
- items = [[1,[2]],[3]]
- Output:
- 10
- Explanation:
D is 3, so 1 and 3 (depth 2) have weight 2 and 2 (depth 3) has weight 1, giving 2 + 2 + 6 = 10.
Constraints
The total number of integers and lists across all levels is at most 3 * 104.
The nesting depth is at most 100.
-100 ≤ each integer ≤ 100. The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(d)