0378MediumHash TableTreeDepth-First SearchBreadth-First SearchSortingBinary Tree

Wall Panel Columns

Tracked in this browser only

Trains the technique from

LeetCode 314Binary Tree Vertical Order Traversal

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 control wall holds labelled junction panels hung in a binary arrangement. The topmost panel occupies column 0. Every panel may carry a lower-left panel and a lower-right panel: the lower-left one hangs one tier down and one column to the left, the lower-right one hangs one tier down and one column to the right.

The wall arrives as panels, a tier-by-tier listing. panels[0] is the top panel's label. The rest of the list is consumed two entries at a time, taking panels in the order they were listed: the next two entries are that panel's lower-left and lower-right labels, where null means no panel hangs there (and therefore contributes no entries of its own). Trailing nulls are omitted, and an empty list means the wall is bare.

Return the labels grouped by column, with the columns ordered from the leftmost to the rightmost. Inside a column, list the labels from the highest tier downwards, and when two panels share both a column and a tier, list the one hanging further left first.

Examples

Example 1

Input: panels = [7, 4, 9]
Output: [[4], [7], [9]]

Panel 4 hangs in column -1, panel 7 in column 0 and panel 9 in column 1.

Example 2

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

Column -1 holds only panel 4. Column 0 holds panel 9 on tier 0 and panel 6 on tier 2. Column 1 holds panel 7 on tier 1 and panel 2 on tier 3.

Example 3

Input: panels = [1, 2, 3, null, 4, 5]
Output: [[2], [1, 4, 5], [3]]

Panels 4 and 5 both land in column 0 on tier 2, and 4 hangs further left, so it is listed first.

Example 4

Input: panels = []
Output: []

The wall is bare, so there are no columns to report.

Constraints

The number of panels on the wall is in the range [0, 100].
-100 <= panel label <= 100

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 vertical_order(panels: list) -> list[list[int]]:

Java

public List<List<Integer>> verticalOrder(Integer[] panels)

The intended approach

Time O(n)Space O(n) for the rebuilt wall, the queue and the returned grouping

Rebuild the wall from the tier-by-tier listing, then sweep it tier by tier with a queue, carrying each panel's column with it: a lower-left panel inherits `col - 1` and a lower-right panel `col + 1`. Appending each label to a bucket keyed by column gives exactly the required order inside a bucket, because a queue reaches higher tiers first and, within a tier, works left to right. Tracking the smallest and largest column seen lets the buckets be emitted in column order without a sort.

Pythonentry point: vertical_order

def _decode(panels):
    if not panels or panels[0] is None:
        return None
    nodes = [[panels[0], None, None]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(panels):
        node = nodes[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(panels):
                break
            label = panels[i]
            i += 1
            if label is not None:
                nodes.append([label, None, None])
                node[slot] = len(nodes) - 1
                order.append(len(nodes) - 1)
    return nodes


def vertical_order(panels):
    # Time O(n) -- one decode pass and one breadth-first pass.
    # Space O(n) for the decoded panels, the queue and the returned grouping.
    nodes = _decode(panels)
    if nodes is None:
        return []
    columns = {}
    lo = 0
    hi = 0
    queue = [(0, 0)]
    head = 0
    while head < len(queue):
        idx, col = queue[head]
        head += 1
        node = nodes[idx]
        if col in columns:
            columns[col].append(node[0])
        else:
            columns[col] = [node[0]]
            if col < lo:
                lo = col
            if col > hi:
                hi = col
        if node[1] is not None:
            queue.append((node[1], col - 1))
        if node[2] is not None:
            queue.append((node[2], col + 1))
    return [columns[c] for c in range(lo, hi + 1)]

The obvious version

Walk the wall depth-first with an explicit stack, recording for every panel its column, its tier and the sequence of left/right steps taken to reach it. Sorting those triples by column, then tier, then step sequence puts the labels in the required order, after which equal columns are grouped.

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 _decode2(panels):
    if not panels or panels[0] is None:
        return None
    nodes = [[panels[0], None, None]]
    order = [0]
    i = 1
    qi = 0
    while qi < len(order) and i < len(panels):
        node = nodes[order[qi]]
        qi += 1
        for slot in (1, 2):
            if i >= len(panels):
                break
            label = panels[i]
            i += 1
            if label is not None:
                nodes.append([label, None, None])
                node[slot] = len(nodes) - 1
                order.append(len(nodes) - 1)
    return nodes


def bf_vertical_order(panels):
    nodes = _decode2(panels)
    if nodes is None:
        return []
    found = []
    stack = [(0, 0, 0, ())]
    while stack:
        idx, col, tier, path = stack.pop()
        node = nodes[idx]
        found.append((col, tier, path, node[0]))
        if node[2] is not None:
            stack.append((node[2], col + 1, tier + 1, path + (1,)))
        if node[1] is not None:
            stack.append((node[1], col - 1, tier + 1, path + (0,)))
    found.sort(key=lambda item: (item[0], item[1], item[2]))
    out = []
    prev = None
    for col, tier, path, label in found:
        if prev is None or col != prev:
            out.append([])
            prev = col
        out[-1].append(label)
    return out

How this problem was checked

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