Restore the Array From Adjacent Pairs

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.

Examples

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]

Solution

Method 1 – Hash Map and Graph Traversal

Intuition

Each number in the array is adjacent to at most two other numbers, except for the endpoints, which are adjacent to only one. By building a graph from the pairs, we can start from an endpoint and reconstruct the array by traversing through the neighbors.

Approach

1. Build a hash map (adjacency list) where each number maps to its neighbors.
2. Find an endpoint (a number with only one neighbor).
3. Start from the endpoint and iteratively add neighbors to the result, avoiding revisiting the previous number.
4. Continue until the array is fully reconstructed.

Complexity

• ⏰ Time complexity: O(n), where n is the number of elements, since we process each pair and reconstruct the array in linear time.
• 🧺 Space complexity: O(n), for the adjacency list and result array.

Code

Java

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] pair : adjacentPairs) {
            graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            graph.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
        }
        int start = 0;
        for (int key : graph.keySet()) {
            if (graph.get(key).size() == 1) {
                start = key;
                break;
            }
        }
        int n = graph.size();
        int[] ans = new int[n];
        ans[0] = start;
        int prev = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            for (int nei : graph.get(ans[i-1])) {
                if (nei != prev) {
                    ans[i] = nei;
                    prev = ans[i-1];
                    break;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int, vector<int>> graph;
        for (auto& p : adjacentPairs) {
            graph[p[0]].push_back(p[1]);
            graph[p[1]].push_back(p[0]);
        }
        int start = 0;
        for (auto& [k, v] : graph) {
            if (v.size() == 1) {
                start = k;
                break;
            }
        }
        int n = graph.size();
        vector<int> ans(n);
        ans[0] = start;
        int prev = INT_MIN;
        for (int i = 1; i < n; ++i) {
            for (int nei : graph[ans[i-1]]) {
                if (nei != prev) {
                    ans[i] = nei;
                    prev = ans[i-1];
                    break;
                }
            }
        }
        return ans;
    }
};

Python

class Solution:
    def restoreArray(self, adjacentPairs: list[list[int]]) -> list[int]:
        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in adjacentPairs:
            graph[u].append(v)
            graph[v].append(u)
        # Find endpoint
        for k, v in graph.items():
            if len(v) == 1:
                start = k
                break
        ans = [start]
        prev = None
        while len(ans) < len(graph):
            curr = ans[-1]
            for nei in graph[curr]:
                if nei != prev:
                    ans.append(nei)
                    prev = curr
                    break
        return ans