Find Largest Value in Each Tree Row
Real-world version: The Heaviest Load on Each DeckThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def largest_values(rig: list) -> list[int]:public int[] largestValues(Integer[] rig)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's