0990MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

The Heaviest Load on Each Deck

Tracked in this browser only

Trains the technique from

LeetCode 515Find Largest Value in Each Tree Row

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 cargo rig is given as the flat list rig. It hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.

A flat list is read level by level: its first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own. A list that ends early leaves the remaining slots empty, and an empty list means no joints at all.

The decks of the rig are its levels: the top joint on its own, then the joints hanging directly off it, then the joints hanging off those, and so on.

Return the heaviest load on each deck, ordered from the top deck downwards. With no joints at all, return an empty list.

Examples

Example 1

Input: rig = [4, 9, 6, 2, 8, null, 7]
Output: [4, 9, 8]

The top deck is the joint loaded 4. Below it hang 9 and 6, the heavier being 9. The bottom deck holds 2, 8 and 7, and the second slot under the joint loaded 6 is empty, so the heaviest down there is 8.

Example 2

Input: rig = [5, 1, 4]
Output: [5, 4]

Two decks: the top joint on its own, then the pair below it, of which 4 is the heavier.

Example 3

Input: rig = [0, null, 3, null, 8]
Output: [0, 3, 8]

Each joint's first slot is empty, so every deck holds exactly one joint and its load is the heaviest there by default.

Constraints

0 <= rig.length <= 30000
The rig holds between 0 and 10^4 joints.
-2^31 <= rig[i] <= 2^31 - 1
The first entry is not null unless the list is empty.

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 largest_values(rig: list) -> list[int]:

Java

public int[] largestValues(Integer[] rig)

The intended approach

Time O(n) over the list's length.Space O(w) for the widest deck.

The list was written deck by deck, so read it back the same way. Hold the positions of the joints on the deck being worked on. The deck below comes from walking those positions in order and claiming two entries of the list for each of them, keeping whichever of the two are not `null`. While claiming, keep the largest load the new deck has shown so far. Once the deck is complete, push that largest onto the answer and move down. Stop as soon as a deck comes out with no joints on it. The top joint is a deck of its own and goes onto the answer before the walk begins. Every entry of the list is claimed exactly once, so the whole thing is a single pass, and nothing is held but the deck currently in hand.

Pythonentry point: largest_values

def largest_values(rig):
    if not rig:
        return []
    n = len(rig)
    out = [rig[0]]
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        best = None
        for _owner in level:
            for _slot in (0, 1):
                if at < n:
                    load = rig[at]
                    if load is not None:
                        nxt.append(at)
                        if best is None or load > best:
                            best = load
                    at += 1
        if not nxt:
            break
        out.append(best)
        level = nxt
    return out

The obvious version

Read the list into a pair of slots for every joint first, then forget about decks and walk the rig depth first from the top, carrying how far down each joint sits. Keep a tally of the heaviest load found at each depth, and read the tally back out in order of depth. Goes by depths gathered on a wandering walk rather than one deck at a time.

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_largest_values(rig):
    if not rig:
        return []
    n = len(rig)
    slot = {}
    level = [0]
    at = 1
    while level and at < n:
        nxt = []
        for owner in level:
            pair = []
            for _s in (0, 1):
                if at < n:
                    pair.append(at if rig[at] is not None else None)
                    at += 1
                else:
                    pair.append(None)
            slot[owner] = pair
            for child in pair:
                if child is not None:
                    nxt.append(child)
        level = nxt
    best = {}
    stack = [(0, 0)]
    while stack:
        node, deep = stack.pop()
        load = rig[node]
        if deep not in best or load > best[deep]:
            best[deep] = load
        for child in slot.get(node, ()):
            if child is not None:
                stack.append((child, deep + 1))
    return [best[deep] for deep in range(len(best))]

How this problem was checked

Reference solution executed against 15 test cases — 15 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