0082HardDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

Best Chamber Run

Tracked in this browser only

Trains the technique from

LeetCode 124Binary Tree Maximum Path Sum

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 survey crew has mapped a cave system that branches downward. Every chamber carries one signed pressure figure in millibars: positive where air is pushed out, negative where air is drawn in.

The map arrives as chambers, a listing of the cave one depth at a time, left to right. Slot 0 holds the mouth chamber. Each chamber that appears in the listing claims the next two free slots for its downhill passages, the left one first and the right one second. A slot holding null means no chamber hangs there, and such a slot claims no slots of its own. Slots holding null at the very end of the listing may be left off.

A run visits one or more chambers, steps only between chambers joined by a single passage, and never revisits a chamber. It may begin and end at any chamber, and it need not touch the mouth. The yield of a run is the total of the pressure figures of the chambers it visits.

Return the largest yield any run can reach. At least one chamber is always mapped, so a run always exists, and the answer can be negative when every chamber draws air in.

Examples

Example 1

Input: chambers = [5, -20, 6]
Output: 11

Starting at the right chamber, stepping up to the mouth and stopping there collects 6 + 5. Extending into the left chamber would cost 20, so the run stops.

Example 2

Input: chambers = [-9, 2, 8, null, null, 11, 4]
Output: 23

The run 11, 8, 4 stays inside the right branch and never pays for the mouth chamber.

Example 3

Input: chambers = [-7]
Output: -7

The only run available is the mouth chamber on its own, so its own figure is the answer.

Constraints

1 <= number of mapped chambers <= 3 * 10^4
-1000 <= chamber pressure <= 1000
chambers[0] is not null
chambers is a valid depth-by-depth listing: no slots follow a null slot's position

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 best_chamber_run(chambers: list[int | None]) -> int:

Java

public int bestChamberRun(Integer[] chambers)

The intended approach

Time O(n)Space O(n)

Rebuild the passage links from the depth-by-depth listing, which puts every chamber after the one above it. Sweeping the listing backwards therefore settles children before parents: for each chamber record the best yield of a run that starts there and only goes downhill, taking a branch only when its own best is positive. The best run overall tops out at some highest chamber, where it may join one downhill branch on each side, so compare that joined total at every chamber.

Pythonentry point: best_chamber_run

def best_chamber_run(chambers):
    n = len(chambers)
    lower_left = [-1] * n
    lower_right = [-1] * n
    listed = [0]
    slot = 1
    head = 0
    while head < len(listed):
        cur = listed[head]
        head += 1
        if slot < n:
            if chambers[slot] is not None:
                lower_left[cur] = slot
                listed.append(slot)
            slot += 1
        if slot < n:
            if chambers[slot] is not None:
                lower_right[cur] = slot
                listed.append(slot)
            slot += 1
    downward = [0] * n
    best = None
    for i in range(n - 1, -1, -1):
        if chambers[i] is None:
            continue
        left, right = lower_left[i], lower_right[i]
        gain_left = downward[left] if left >= 0 and downward[left] > 0 else 0
        gain_right = downward[right] if right >= 0 and downward[right] > 0 else 0
        downward[i] = chambers[i] + (gain_left if gain_left > gain_right else gain_right)
        joined = chambers[i] + gain_left + gain_right
        if best is None or joined > best:
            best = joined
    return best

The obvious version

Treat the passages as an undirected graph and enumerate every run outright: from each chamber, walk depth-first over unvisited neighbours and score every prefix of every walk. Exponential in the worst case, but it never reasons about downhill gains.

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_best_chamber_run(chambers):
    n = len(chambers)
    reading = {0: chambers[0]}
    passages = {0: []}
    listed = [0]
    slot = 1
    head = 0
    while head < len(listed):
        cur = listed[head]
        head += 1
        for _ in range(2):
            if slot < n:
                if chambers[slot] is not None:
                    reading[slot] = chambers[slot]
                    passages.setdefault(cur, []).append(slot)
                    passages.setdefault(slot, []).append(cur)
                    listed.append(slot)
                slot += 1
    best = [None]

    def walk(here, visited, total):
        if best[0] is None or total > best[0]:
            best[0] = total
        for nxt in passages.get(here, []):
            if nxt in visited:
                continue
            visited.add(nxt)
            walk(nxt, visited, total + reading[nxt])
            visited.remove(nxt)

    for start in reading:
        walk(start, {start}, reading[start])
    return best[0]

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