0126EasyTreeDepth-First SearchBinary TreeDP on Trees

Widest Gallery Walk

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.

A gallery branches outward from its atrium. Every room has at most two doorways leading further out, and each room carries one signed humidity reading.

The floor plan arrives as rooms, which lists the gallery one level at a time, left to right. Position 0 holds the atrium. Each room named in the listing claims the next two free positions for its outward doorways, the left doorway first and the right one second. A position holding null means no room hangs there, and it claims no positions of its own. Trailing null positions may be left off the listing.

A walk starts in some room, passes through doorways, and never enters a room twice. Its span is the number of doorways it passes through. The walk may start and end anywhere and does not have to reach the atrium.

Return the largest span any walk in the gallery can reach. A gallery with a lone atrium has a largest span of 0. The humidity readings never affect the answer.

Examples

Example 1

Input: rooms = [12, -3, 40, 7, 6]
Output: 3

Walking from the room at position 3 out through position 1, the atrium, and on to position 2 passes through 3 doorways, and nothing longer exists.

Example 2

Input: rooms = [9, 1, null, 5, 7, 8, null, null, -5]
Output: 4

The gallery leans to one side. The widest walk runs position 5, position 3, position 1, position 4, position 8 for 4 doorways, and it never enters the atrium; any walk that does turn around at the atrium passes through only 3.

Example 3

Input: rooms = [0]
Output: 0

The atrium stands alone, so every walk passes through no doorways at all.

Constraints

1 <= number of listed rooms <= 10^4
-100 <= humidity reading <= 100
rooms[0] is not null
rooms is a valid level-by-level listing: no room hangs below a null 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 widest_gallery_walk(rooms: list[int | None]) -> int:

Java

public int widestGalleryWalk(Integer[] rooms)

The intended approach

Time O(n)Space O(n)

Any walk turns around at exactly one room that is closest to the atrium, where it dives into at most one branch on each side. So for every room work out `drop`, the doorway count of the longest walk heading straight outward from it, then score that room as the sum of the two outward counts and keep the best score. Because the listing always names a room before the rooms hanging off it, reading the positions from the back forward settles both branches before their room is scored.

Pythonentry point: widest_gallery_walk

def widest_gallery_walk(rooms):
    n = len(rooms)
    left = [-1] * n
    right = [-1] * n
    listed = [0]
    slot = 1
    head = 0
    while head < len(listed):
        cur = listed[head]
        head += 1
        if slot < n:
            if rooms[slot] is not None:
                left[cur] = slot
                listed.append(slot)
            slot += 1
        if slot < n:
            if rooms[slot] is not None:
                right[cur] = slot
                listed.append(slot)
            slot += 1
    drop = [0] * n
    widest = 0
    for i in range(n - 1, -1, -1):
        if rooms[i] is None:
            continue
        down_left = drop[left[i]] + 1 if left[i] >= 0 else 0
        down_right = drop[right[i]] + 1 if right[i] >= 0 else 0
        if down_left + down_right > widest:
            widest = down_left + down_right
        drop[i] = down_left if down_left > down_right else down_right
    return widest

The obvious version

Rebuild the doorways as an undirected graph, then breadth-first search from every room in turn and record the largest doorway count reached. O(n^2) and it never reasons about outward depths.

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_widest_gallery_walk(rooms):
    n = len(rooms)
    doors = {0: []}
    listed = [0]
    slot = 1
    head = 0
    while head < len(listed):
        cur = listed[head]
        head += 1
        for _ in range(2):
            if slot < n:
                if rooms[slot] is not None:
                    doors.setdefault(cur, []).append(slot)
                    doors.setdefault(slot, []).append(cur)
                    listed.append(slot)
                slot += 1
    widest = 0
    for start in doors:
        seen = {start: 0}
        queue = [start]
        head = 0
        while head < len(queue):
            here = queue[head]
            head += 1
            for nxt in doors.get(here, []):
                if nxt not in seen:
                    seen[nxt] = seen[here] + 1
                    queue.append(nxt)
        for room in seen:
            if seen[room] > widest:
                widest = seen[room]
    return widest

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