Show problems as
Classic problem #1743MediumArrayHash TableDepth-First Search

Restore the Array From Adjacent Pairs

Real-world version: Rebuild the Relay Line-Up
Tracked in this browser only
Read Restore the Array From Adjacent Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def restore_array(adjacentPairs: list[list[int]]) -> list[int]:
Java
public int[] restoreArray(int[][] adjacentPairs)

More on the same topics