0676MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Heaviest Tier of the Reporting Chart

Tracked in this browser only

Trains the technique from

LeetCode 1161Maximum Level Sum of a Binary Tree

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.

A company files a reporting chart. One unit sits at the top, and every unit has at most two units reporting to it, held in a first slot and a second slot; either slot may be empty. Each unit files a monthly balance, which may be negative.

The chart arrives as the flat list units, written tier by tier. units[0] is the balance of the top unit. Reading the list from left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, and null marks an empty slot. An entry that is null claims no positions of its own. If the list ends early, the slots that were never written are empty.

Tiers are numbered from 1: the top unit is on tier 1, the units reporting to it are on tier 2, and so on. A tier's total is the sum of the balances of the units on it.

Return the number of the tier with the largest total. If more than one tier ties for the largest total, return the smallest such tier number.

Examples

Example 1

Input: units = [4, 7, 9, 6, 5, null, 8]
Output: 3

Tier 1 holds the top unit and totals 4. Tier 2 holds 7 and 9 and totals 16. The unit filing 7 owns the next two positions, 6 and 5; the unit filing 9 owns an empty slot and the unit filing 8. So tier 3 holds 6, 5 and 8 and totals 19.

Example 2

Input: units = [5, 2, 3]
Output: 1

Tier 1 totals 5, and tier 2 holds 2 and 3, which also totals 5. The two tiers tie, so the smaller tier number is returned.

Example 3

Input: units = [8, null, 6, null, 7]
Output: 1

The top unit's first slot is empty and its second slot holds the unit filing 6, so tier 2 totals 6. That unit's slots are empty and 7 in turn, so tier 3 totals 7. Tier 1 totals 8, the largest of the three.

Constraints

The chart holds between 1 and 10^4 units.
1 <= units.length <= 3 * 10^4
-10^5 <= units[i] <= 10^5
units[0] is not null.

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 heaviest_tier(units: list) -> int:

Java

public int heaviestTier(Integer[] units)

The intended approach

Time O(n) where n is the length of the list: every position is read once.Space O(w) where w is the largest number of units on one tier.

The flat list can be read tier by tier without building the chart. Keep the balances of the filled units on the current tier; if there are `k` of them, the next `2k` positions of the list hold their slots, so the filled entries in that window are exactly the next tier. Add up each tier as it is read, remember the largest total and the tier it came from, and replace the running best only on a strictly larger total so an earlier tier keeps a tie. Stop when the window holds no filled entry or the list runs out.

Pythonentry point: heaviest_tier

def heaviest_tier(units):
    # tier by tier over the flat list: the k filled units of a tier own the next 2k positions
    tier_vals = [units[0]]
    idx = 1
    best_total = units[0]
    best_tier = 1
    tier = 1
    while idx < len(units):
        slots = 2 * len(tier_vals)
        nxt = []
        stop = min(idx + slots, len(units))
        for j in range(idx, stop):
            if units[j] is not None:
                nxt.append(units[j])
        idx += slots
        tier += 1
        if not nxt:
            break
        total = 0
        for v in nxt:
            total += v
        if total > best_total:
            best_total = total
            best_tier = tier
        tier_vals = nxt
    return best_tier

The obvious version

Rebuild the chart from the flat list: keep a queue of filled units and hand each of them the next two positions as its slots, recording the links. Then walk the rebuilt chart from the top with an explicit stack, carrying each unit's tier number and adding its balance into a tally per tier. Finally scan the tiers in increasing order and keep the first one that reaches the largest tally.

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_heaviest_tier(units):
    n = len(units)
    first = {}
    second = {}
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue):
        node = queue[head]
        head += 1
        for which in (0, 1):
            if slot >= n:
                break
            if units[slot] is not None:
                if which == 0:
                    first[node] = slot
                else:
                    second[node] = slot
                queue.append(slot)
            slot += 1
    totals = {}
    stack = [(0, 1)]
    while stack:
        node, depth = stack.pop()
        totals[depth] = totals.get(depth, 0) + units[node]
        if node in first:
            stack.append((first[node], depth + 1))
        if node in second:
            stack.append((second[node], depth + 1))
    best_depth = None
    best = None
    for depth in sorted(totals):
        if best is None or totals[depth] > best:
            best = totals[depth]
            best_depth = depth
    return best_depth

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 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