Formatted question description: https://leetcode.ca/all/1743.html

# 1743. Restore the Array From Adjacent Pairs

## Level

Medium

## Description

There is an integer array `nums`

that consists of `n`

**unique** elements, but you have forgotten it. However, you do remember every pair of adjacent elements in `nums`

.

You are given a 2D integer array `adjacentPairs`

of size `n - 1`

where each `adjacentPairs[i] = [u_i, v_i]`

indicates that the elements `u_i`

and `v_i`

are adjacent in `nums`

.

It is guaranteed that every adjacent pair of elements `nums[i]`

and `nums[i+1]`

will exist in `adjacentPairs`

, either as `[nums[i], nums[i+1]]`

or `[nums[i+1], nums[i]]`

. The pairs can appear **in any order**.

Return *the original array nums. If there are multiple solutions, return any of them*.

**Example 1:**

**Input:** adjacentPairs = [[2,1],[3,4],[3,2]]

**Output:** [1,2,3,4]

**Explanation:** This array has all its adjacent pairs in adjacentPairs.

Notice that adjacentPairs[i] may not be in left-to-right order.

**Example 2:**

**Input:** adjacentPairs = [[4,-2],[1,4],[-3,1]]

**Output:** [-2,4,1,-3]

**Explanation:** There can be negative numbers.

Another solution is [-3,1,4,-2], which would also be accepted.

**Example 3:**

**Input:** adjacentPairs = [[100000,-100000]]

**Output:** [100000,-100000]

**Constraints:**

`nums.length == n`

`adjacentPairs.length == n - 1`

`adjacentPairs[i].length == 2`

`2 <= n <= 10^5`

`-10^5 <= nums[i], ui, vi <= 10^5`

- There exists some
`nums`

that has`adjacentPairs`

as its pairs.

## Solution

All elements in `nums`

occur twice in `adjacentPairs`

except the two elements that are at the start and the end of `nums`

. Therefore, start from the two elements that occur only once in `adjacentPairs`

, put them at index 0 and index `n - 1`

of `nums`

respectively. The two elements at indices 1 and `n - 2`

can be determined as well. For `i`

from 1 to `n - 2`

, obtain the adjacent numbers of `nums[i]`

and set `nums[i + 1]`

as the remaining element (that is differnet from `nums[i - 1]`

). Finally, return `nums`

.

```
class Solution {
public int[] restoreArray(int[][] adjacentPairs) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int[] adjacentPair : adjacentPairs) {
int num1 = adjacentPair[0], num2 = adjacentPair[1];
List<Integer> list1 = map.getOrDefault(num1, new ArrayList<Integer>());
List<Integer> list2 = map.getOrDefault(num2, new ArrayList<Integer>());
list1.add(num2);
list2.add(num1);
map.put(num1, list1);
map.put(num2, list2);
}
int length = adjacentPairs.length + 1;
int[] nums = new int[length];
boolean flag = false;
Set<Integer> set = map.keySet();
for (int num : set) {
List<Integer> list = map.get(num);
if (list.size() == 1) {
if (!flag) {
nums[0] = num;
nums[1] = list.get(0);
flag = true;
} else {
nums[length - 1] = num;
nums[length - 2] = list.get(0);
}
}
}
for (int i = 1; i < length - 1; i++) {
int num = nums[i];
List<Integer> list = map.get(num);
for (int adjacent : list) {
if (adjacent != nums[i - 1]) {
nums[i + 1] = adjacent;
break;
}
}
}
return nums;
}
}
```