0399MediumDepth-First SearchBreadth-First Search

Tiered Ledger Adjustments

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An auditor hands you a file of ledger adjustments, grouped and regrouped by department. The file is supplied as JSON: entries is a list, and each slot in a list holds either a signed integer, which is one adjustment, or a further list, which is a nested group. A group is allowed to be empty.

The tier of an adjustment is the number of groups wrapped around it. Adjustments written straight into entries sit at tier 1, adjustments inside a group that sits straight in entries are at tier 2, and each further layer of nesting adds one.

Return the sum of value * tier over every adjustment the file contains.

Examples

Example 1

Input: entries = [3,[5,-2],7]
Output: 16

The adjustments 3 and 7 sit at tier 1, while 5 and -2 sit at tier 2, giving 3 + 7 + 2*5 + 2*(-2) = 16.

Example 2

Input: entries = [[[4]]]
Output: 12

Three groups wrap the single adjustment 4, so its tier is 3 and the total is 3*4 = 12.

Example 3

Input: entries = [-8]
Output: -8

One tier-1 adjustment, and adjustments may be negative, so the total is 1*(-8) = -8.

Example 4

Input: entries = [2,[3,[-1,[6]]]]
Output: 29

The tiers are 1 for 2, 2 for 3, 3 for -1 and 4 for 6, giving 2 + 2*3 + 3*(-1) + 4*6 = 29.

Example 5

Input: entries = [[],9]
Output: 9

The empty group holds no adjustments and contributes nothing, leaving the tier-1 adjustment 9.

Constraints

1 <= entries.length <= 50
Every adjustment is in the range [-100, 100].
No adjustment sits at a tier greater than 50.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def depth_sum(entries: list) -> int:

Java

public int depthSum(List<NestedInteger> entries)

The intended approach

Time O(N) where N is the number of adjustments plus groups in the fileSpace O(N) for the explicit stack in the worst case

Carry the tier alongside each group on an explicit stack rather than recursing, so a file nested 50 deep costs nothing extra. Pop a (group, tier) pair, add `value * tier` for every integer slot, and push each nested group back with its tier raised by one.

Pythonentry point: depth_sum

def depth_sum(entries):
    # Time O(N) where N counts every adjustment and every group in the file:
    # each is pushed once and popped once. Space O(N) for the explicit stack,
    # which is used instead of recursion so a 50-deep file is no risk.
    total = 0
    stack = [(entries, 1)]
    while stack:
        group, tier = stack.pop()
        for slot in group:
            if isinstance(slot, list):
                stack.append((slot, tier + 1))
            else:
                total += slot * tier
    return total

The obvious version

Recursive descent: a helper takes a group and its tier, weights the integers it sees directly, and adds the value returned by calling itself on each nested group.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_depth_sum(entries):
    def walk(group, tier):
        running = 0
        for slot in group:
            if isinstance(slot, list):
                running += walk(slot, tier + 1)
            else:
                running += slot * tier
        return running

    return walk(entries, 1)

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in