# Restore the Array From Adjacent Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/restore-the-array-from-adjacent-pairs)
Canonical: https://scaleengineer.com/dsa/problems/restore-the-array-from-adjacent-pairs
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, Hash Table
**Companies:** [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## Problem
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] = [ui, vi]` indicates that the elements `ui` and `vi` 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 <= 105`
* `-105 <= nums[i], ui, vi <= 105`
* There exists some `nums` that has `adjacentPairs` as its pairs.

# Approaches
## Iterative Search
This approach reconstructs the array by repeatedly scanning the input `adjacentPairs` to find the next element in the sequence. It starts by identifying an endpoint and then iteratively builds the array element by element without building an explicit graph.
**Time:** O(N^2), where N is the number of elements in the array. The outer loop runs N-1 times, and inside it, we iterate through the `adjacentPairs` array of size N-1. This results in a quadratic runtime. · **Space:** O(N), where N is the number of elements in the array. This space is used to store the frequency counts of numbers and the result array.
**Pros:** Conceptually straightforward without needing explicit graph data structures.; Relatively easy to implement for those less familiar with graphs.
**Cons:** Highly inefficient due to the nested loop structure, where the entire `adjacentPairs` list is scanned for each element of the output array.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger test cases.
### Explanation
This method reconstructs the array by iteratively finding the next adjacent element. It avoids building an explicit graph structure but pays a price in performance.

The algorithm proceeds as follows:
1.  First, we need a starting point. The endpoints of the original array are unique in that they only have one neighbor, while all other elements have two. We can find an endpoint by counting the frequency of each number in the `adjacentPairs`. A number appearing only once must be an endpoint.
2.  We initialize our result array with this starting number.
3.  We then loop `n-1` times to find the remaining elements. In each iteration, we search through the `adjacentPairs` list to find a pair that contains the last element added to our result (`curr`).
4.  To ensure we move forward along the path, we keep track of the `prev` element and pick the neighbor of `curr` that is not `prev`.
5.  Once we find the next element, we append it to our result and continue the process until the array is fully reconstructed.

This repeated scanning of the `adjacentPairs` list in each step leads to a quadratic time complexity.

```java
import java.util.*;

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        int n = adjacentPairs.length + 1;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int[] pair : adjacentPairs) {
            counts.put(pair[0], counts.getOrDefault(pair[0], 0) + 1);
            counts.put(pair[1], counts.getOrDefault(pair[1], 0) + 1);
        }

        int startNode = -1;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                startNode = entry.getKey();
                break;
            }
        }

        int[] result = new int[n];
        result[0] = startNode;
        int curr = startNode;
        int prev = Integer.MIN_VALUE; // A value guaranteed not to be in the array

        for (int i = 1; i < n; i++) {
            // Search for the next element by scanning all pairs
            for (int[] pair : adjacentPairs) {
                if (pair[0] == curr && pair[1] != prev) {
                    result[i] = pair[1];
                    break;
                } else if (pair[1] == curr && pair[0] != prev) {
                    result[i] = pair[0];
                    break;
                }
            }
            prev = curr;
            curr = result[i];
        }
        return result;
    }
}
```
### Algorithm
- Create a map to count the occurrences of each number in `adjacentPairs`.
- Find a number that appears only once. This will be one of the endpoints of the array.
- Initialize the result array `ans` with this starting endpoint.
- Set a `prev` variable to a sentinel value (one that cannot be in the input) and `curr` to the starting endpoint.
- Loop `n-1` times to find the rest of the elements:
  - In each iteration, scan the entire `adjacentPairs` array.
  - Find a pair `[u, v]` where one element equals `curr` and the other does not equal `prev`.
  - The element that is not `prev` is the next element in the sequence.
  - Add this next element to the `ans` array.
  - Update `prev` to `curr` and `curr` to the newly added element.
- Return the `ans` array.

## Graph Traversal with Hash Map
This optimal approach models the problem as finding a path in a graph. The numbers are treated as nodes and the adjacent pairs as edges. By building an adjacency list using a hash map, we can easily find an endpoint (a node with only one edge) and then traverse the graph in linear time to reconstruct the original array.
**Time:** O(N), where N is the number of elements. Building the graph takes O(N) time as we process N-1 pairs. Finding the start node takes O(N) in the worst case. The final traversal visits each node and edge once, which is also O(N). · **Space:** O(N), where N is the number of elements. This space is required to store the graph's adjacency list in the `HashMap` and the result array. The map will store N nodes and 2*(N-1) total neighbor entries.
**Pros:** Highly efficient with linear time complexity.; Scales well for large inputs, which is crucial given the constraints (N up to 10^5).; It's a standard and robust technique for path-related problems.
**Cons:** Requires familiarity with graph representations like adjacency lists.; Slightly more complex to implement than the naive approach due to the setup of the graph data structure.
### Explanation
The most efficient way to solve this problem is to view it as a graph problem. Each number is a node, and an adjacent pair `[u, v]` represents an edge connecting nodes `u` and `v`. Since the original array was a simple sequence of unique numbers, the resulting graph is a simple path.

The core idea is to:
1.  **Build the Graph:** Construct an adjacency list representation of the graph using a `HashMap`. The keys will be the numbers (nodes), and the values will be lists of their neighbors. We iterate through `adjacentPairs`, and for each pair `[u, v]`, we add `v` to `u`'s adjacency list and `u` to `v`'s list.
2.  **Find an Endpoint:** In a path graph, the two endpoints have a degree of 1 (only one neighbor), while all intermediate nodes have a degree of 2. We can find a starting point for our traversal by iterating through our map and finding any node whose adjacency list has a size of 1.
3.  **Traverse the Path (DFS):** Starting from the endpoint, we perform a traversal to reconstruct the array. We build the result array one element at a time. At each step, we look at the neighbors of the current node. Since we are traversing a path, there will be only one unvisited neighbor (the one not equal to the `previous` node). We move to that neighbor, add it to our result, and repeat until all `n` elements are found.

This approach processes each pair and each number a constant number of times, resulting in a linear time complexity.

```java
import java.util.*;

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // 1. Build the graph
        for (int[] pair : adjacentPairs) {
            graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            graph.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
        }

        // 2. Find the starting node (an endpoint with degree 1)
        int startNode = -1;
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            if (entry.getValue().size() == 1) {
                startNode = entry.getKey();
                break;
            }
        }

        // 3. Traverse the path to reconstruct the array
        int n = adjacentPairs.length + 1;
        int[] result = new int[n];
        int curr = startNode;
        int prev = Integer.MIN_VALUE; // Sentinel value

        for (int i = 0; i < n; i++) {
            result[i] = curr;
            List<Integer> neighbors = graph.get(curr);
            
            // Find the next node in the path
            // For the last node, neighbors will be just prev, loop won't run, curr won't be updated, which is fine.
            for (int neighbor : neighbors) {
                if (neighbor != prev) {
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }

        return result;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, List<Integer>>` to serve as an adjacency list for the graph.
- Iterate through `adjacentPairs`. For each pair `[u, v]`, add `v` to `u`'s neighbor list and `u` to `v`'s neighbor list.
- Find the starting node for the traversal. Iterate through the `HashMap` to find a key whose value (list of neighbors) has a size of 1. This node is an endpoint of the original array.
- Initialize the result array `ans` of size `N`.
- Start a traversal from the identified endpoint. Use a `prev` variable to keep track of the previously visited node to avoid going backward.
- In a loop for `N` iterations, add the `curr` node to `ans`, find its unvisited neighbor (the one not equal to `prev`), and update `prev` and `curr`.
- Return the `ans` array.

# Solutions
### CSharp

```csharp
public class Solution { public int [] RestoreArray ( int [][] adjacentPairs ) { int n = adjacentPairs . Length + 1 ; Dictionary < int , List < int >> g = new Dictionary < int , List < int >>(); foreach ( int [] e in adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; if (! g . ContainsKey ( a )) { g [ a ] = new List < int >(); } if (! g . ContainsKey ( b )) { g [ b ] = new List < int >(); } g [ a ]. Add ( b ); g [ b ]. Add ( a ); } int [] ans = new int [ n ]; foreach ( var entry in g ) { if ( entry . Value . Count == 1 ) { ans [ 0 ] = entry . Key ; ans [ 1 ] = entry . Value [ 0 ]; break ; } } for ( int i = 2 ; i < n ; ++ i ) { List < int > v = g [ ans [ i - 1 ]]; ans [ i ] = v [ 1 ] == ans [ i - 2 ] ? v [ 0 ] : v [ 1 ]; } return ans ; } }
```

### Java

```java
class Solution { public int [] restoreArray ( int [][] adjacentPairs ) { int n = adjacentPairs . length + 1 ; Map < Integer , List < Integer >> g = new HashMap <>(); for ( int [] e : adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; g . computeIfAbsent ( a , k -> new ArrayList <>()). add ( b ); g . computeIfAbsent ( b , k -> new ArrayList <>()). add ( a ); } int [] ans = new int [ n ]; for ( Map . Entry < Integer , List < Integer >> entry : g . entrySet ()) { if ( entry . getValue (). size () == 1 ) { ans [ 0 ] = entry . getKey (); ans [ 1 ] = entry . getValue (). get ( 0 ); break ; } } for ( int i = 2 ; i < n ; ++ i ) { List < Integer > v = g . get ( ans [ i - 1 ]); ans [ i ] = v . get ( 1 ) == ans [ i - 2 ] ? v . get ( 0 ) : v . get ( 1 ); } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > restoreArray ( vector < vector < int >>& adjacentPairs ) { int n = adjacentPairs . size () + 1 ; unordered_map < int , vector < int >> g ; for ( auto & e : adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); } vector < int > ans ( n ); for ( auto & [ k , v ] : g ) { if ( v . size () == 1 ) { ans [ 0 ] = k ; ans [ 1 ] = v [ 0 ]; break ; } } for ( int i = 2 ; i < n ; ++ i ) { auto v = g [ ans [ i - 1 ]]; ans [ i ] = v [ 0 ] == ans [ i - 2 ] ? v [ 1 ] : v [ 0 ]; } return ans ; } };
```

### Python

```python
class Solution : def restoreArray ( self , adjacentPairs : List [ List [ int ]]) -> List [ int ]: g = defaultdict ( list ) for a , b in adjacentPairs : g [ a ]. append ( b ) g [ b ]. append ( a ) n = len ( adjacentPairs ) + 1 ans = [ 0 ] * n for i , v in g . items (): if len ( v ) == 1 : ans [ 0 ] = i ans [ 1 ] = v [ 0 ] break for i in range ( 2 , n ): v = g [ ans [ i - 1 ]] ans [ i ] = v [ 0 ] if v [ 1 ] == ans [ i - 2 ] else v [ 1 ] return ans
```