0157MediumArrayHash TableDivide and ConquerTreeBinary Tree

Cave Survey Rebuild

Tracked in this browser only

Trains the technique from

LeetCode 105Construct Binary Tree from Preorder and Inorder 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 caving club has surveyed a dry cave system. Each chamber carries its own depth marker, no two markers alike, and from any chamber at most two passages lead onward: a near one and a far one. A single chamber serves as the entrance.

Two teams walked the system, and both always took a chamber's near passage before its far passage.

The descent team wrote down a chamber's marker the moment they stepped into it, then covered everything behind its near passage, then everything behind its far passage. Their log arrives as entry_order.
The wall team covered everything behind the near passage first, wrote down the marker of the chamber they were standing in next, and covered the far passage last. Their log arrives as wall_order.

Because the markers are all different, exactly one layout produces both logs. Rebuild it and hand it back level by level, beginning with the entrance. Every chamber that exists puts two slots on the level below it, near slot before far slot, holding either the marker of the chamber found there or null when that passage does not exist. Any null slots trailing after the final marker are left off the answer.

Examples

Example 1

Input: entry_order = [10, 4, -8, 6, 17, 25, 20], wall_order = [-8, 4, 6, 10, 17, 20, 25]
Output: [10, 4, 17, -8, 6, null, 25, null, null, null, null, 20]

Marker 10 is the entrance, and the wall log puts -8, 4 and 6 on its near side, so 4 heads that branch with -8 and 6 hanging off it. On the far side 17 has no near passage, and its far passage leads to 25, whose own near passage reaches 20.

Example 2

Input: entry_order = [1, -9, 4, 2], wall_order = [-9, 2, 4, 1]
Output: [1, -9, null, null, 4, 2]

Every chamber sits on the near side of the entrance, so 1 has no far passage at all, and the branch below alternates sides on the way down.

Example 3

Input: entry_order = [42], wall_order = [42]
Output: [42]

A system of one chamber has no passages, so the answer holds just the entrance marker with no trailing null slots.

Constraints

1 <= entry_order.length <= 3000
wall_order.length == entry_order.length
-3000 <= entry_order[i], wall_order[i] <= 3000
All markers in entry_order are distinct, and wall_order is a rearrangement of entry_order
The two logs are guaranteed to come from one real cave system, walked as described

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 rebuild_cave(entry_order: list[int], wall_order: list[int]) -> list:

Java

public Integer[] rebuildCave(int[] entryOrder, int[] wallOrder)

The intended approach

Time O(n)Space O(n) for the marker lookup table, the range stack and the rebuilt layout

The descent log hands you chambers in exactly the order you want to create them: its next unused marker is always the top chamber of the range you are currently filling. The wall log tells you how a range splits, because the markers before a chamber's position in that log are precisely its near side. Index the wall log once into a lookup table so a split costs constant time, then carry an explicit stack of ranges instead of recursion, popping the near range before the far one so the descent cursor stays in step. Finally sweep the finished layout level by level and trim the trailing empty slots.

Pythonentry point: rebuild_cave

def rebuild_cave(entry_order, wall_order):
    # each chamber is created and read once: O(n) time, O(n) space
    n = len(entry_order)
    if n == 0:
        return []
    # marker -> position in the wall log, so each split is O(1)
    where = {label: i for i, label in enumerate(wall_order)}
    cursor = 0
    root = None
    # frame = (lo, hi, parent, side): 1 = near slot, 2 = far slot
    frames = [(0, n - 1, None, 0)]
    while frames:
        lo, hi, parent, side = frames.pop()
        if lo > hi:
            continue
        label = entry_order[cursor]
        cursor += 1
        node = [label, None, None]
        if parent is None:
            root = node
        elif side == 1:
            parent[1] = node
        else:
            parent[2] = node
        mid = where[label]
        # far range is pushed first so the near range is handled first
        frames.append((mid + 1, hi, node, 2))
        frames.append((lo, mid - 1, node, 1))
    out = []
    queue = [root]
    head = 0
    while head < len(queue):
        node = queue[head]
        head += 1
        if node is None:
            out.append(None)
            continue
        out.append(node[0])
        queue.append(node[1])
        queue.append(node[2])
    while out and out[-1] is None:
        out.pop()
    return out

The obvious version

Recursive split with fresh copies: scan the wall log for the current top marker, slice both logs in two and recurse. The scan and the slicing make it O(n^2). Serialising is done differently too, by dropping every chamber into a numbered slot of a complete layout and then reading the slots back level by level.

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_rebuild_cave(entry_order, wall_order):
    def build(pre, ino):
        if not pre:
            return None
        label = pre[0]
        k = ino.index(label)
        return (label, build(pre[1:k + 1], ino[:k]), build(pre[k + 1:], ino[k + 1:]))

    root = build(list(entry_order), list(wall_order))
    if root is None:
        return []
    slots = {}

    def place(node, idx):
        if node is None:
            return
        slots[idx] = node[0]
        place(node[1], 2 * idx + 1)
        place(node[2], 2 * idx + 2)

    place(root, 0)
    top = max(slots)
    out = []
    d = 0
    while (1 << d) - 1 <= top:
        for i in range((1 << d) - 1, (1 << (d + 1)) - 1):
            if i == 0 or ((i - 1) // 2) in slots:
                out.append(slots.get(i))
        d += 1
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

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