0570MediumArrayHash TableDepth-First Search

Rebuild the Relay Line-Up

Tracked in this browser only

Trains the technique from

LeetCode 1743Restore the Array From Adjacent Pairs

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 relay race was run by n runners standing in a line, each wearing a distinct number. The line-up itself was lost, but every handover was recorded: adjacentPairs[i] = [u_i, v_i] says that the runners numbered u_i and v_i stood next to each other. The handovers are listed in no particular order, and the two numbers inside one handover are in no particular order either.

Rebuild the line-up. A line-up read from either end fits the same handovers, so to make the answer unique, return the reading that starts with the smaller of the two numbers at the ends of the line.

The recorded handovers always come from some line-up of distinct numbers.

Examples

Example 1

Input: adjacentPairs = [[4, 8], [2, 4], [8, 6], [2, 5]]
Output: [5, 2, 4, 8, 6]

The line-up 5, 2, 4, 8, 6 hands over between 5 and 2, 2 and 4, 4 and 8, and 8 and 6, which is exactly the recorded set. Its ends are 5 and 6, so the reading opening with 5 is returned.

Example 2

Input: adjacentPairs = [[9, 1], [1, 5]]
Output: [5, 1, 9]

Runner 1 stood between runners 9 and 5, so the ends are 5 and 9 and the required reading opens with 5.

Example 3

Input: adjacentPairs = [[7, -3]]
Output: [-3, 7]

Two runners stood side by side, and -3 is the smaller of the two end numbers.

Constraints

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 10^5
-10^5 <= nums[i], u_i, v_i <= 10^5
All numbers in the line-up are distinct.
The handovers come from at least one valid line-up.
The returned line-up starts with the smaller of its two end numbers.

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 restore_array(adjacentPairs: list[list[int]]) -> list[int]:

Java

public int[] restoreArray(int[][] adjacentPairs)

The intended approach

Time O(n) to build the map and O(n) to walk the chain.Space O(n) for the map and the returned line-up.

Collect the handovers into a map from a runner number to the numbers recorded beside it. The two runners at the ends of the line appear in exactly one handover each, so they are the entries with a single neighbour; take the smaller of those two as the opening number, which is what the required reading asks for. Then walk the chain in a loop, at each step choosing the neighbour that is not the number just left behind, until the line-up holds every runner. The walk is iterative, so the depth of the chain is not a concern.

Pythonentry point: restore_array

def restore_array(adjacentPairs):
    # O(n) time, O(n) space: build the neighbour map, start at whichever of the two
    # single-neighbour values is smaller, and walk the chain with a loop rather
    # than recursion so a line-up of 100000 values is safe.
    neighbours = {}
    for u, v in adjacentPairs:
        neighbours.setdefault(u, []).append(v)
        neighbours.setdefault(v, []).append(u)
    ends = [value for value, near in neighbours.items() if len(near) == 1]
    start = min(ends)
    out = [start]
    previous = None
    current = start
    while len(out) < len(neighbours):
        step = None
        for candidate in neighbours[current]:
            if candidate != previous:
                step = candidate
                break
        out.append(step)
        previous = current
        current = step
    return out

The obvious version

Enumerate every arrangement of the recorded numbers, turn each arrangement into the multiset of neighbouring pairs it would produce, and return the first arrangement whose multiset matches the recorded handovers and which starts with the smaller of its two end numbers.

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_restore_array(adjacentPairs):
    import itertools
    values = set()
    for u, v in adjacentPairs:
        values.add(u)
        values.add(v)
    target = sorted(sorted(p) for p in adjacentPairs)
    for perm in itertools.permutations(sorted(values)):
        made = sorted(sorted([perm[i], perm[i + 1]]) for i in range(len(perm) - 1))
        if made == target:
            if perm[0] < perm[-1]:
                return list(perm)
    return []

How this problem was checked

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