Skip to main content

Hashing

Restore the Array From Adjacent Pairs Solution In C++/Java/Python/Javascript

Problem 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] = [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

Input: adjacentPairs = [[5, 6], [2, 5], [3, 2]]
Output: [3, 2, 5, 6]
Explanation: From the input, we know that:
5 is adjacent to 6 (from [5, 6]),
2 is adjacent to 5 (from [2, 5]),
3 is adjacent to 2 (from [3, 2]).
Using this information, we can construct the graph (adjacency list):
6 → [5], 5 → [6, 2], 2 → [5, 3], 3 → [2]
From the graph:
Nodes 3 and 6 are endpoints because they each have only one neighbor.
Start from 3 (an endpoint) and traverse the graph:
Start with 3 → go to 2 → then to 5 → finally to 6.
The reconstructed array is [3, 2, 5, 6]. (Another valid solution could be [6, 5, 2, 3] if you start traversal from 6.)

Input: adjacentPairs = [[8, 10], [5, 8], [5, 3], [10, 12]]
Output: [3, 5, 8, 10, 12]
Explanation:
From the input, we know that:
8 is adjacent to 10 (from [8, 10]),
5 is adjacent to 8 (from [5, 8]),
5 is also adjacent to 3 (from [5, 3]),
10 is adjacent to 12 (from [10, 12]).
Using this information, we can construct the graph (adjacency list):
8 → [10, 5], 10 → [8, 12], 5 → [8, 3], 3 → [5], 12 → [10]
From the graph:
Nodes 3 and 12 are endpoints because they each have only one neighbor.
Start from 3 (an endpoint) and traverse the graph:
Start with 3 → go to 5 → then to 8 → then to 10 → finally to 12.
The reconstructed array is [3, 5, 8, 10, 12]. (Another valid solution could be [12, 10, 8, 5, 3] if you start traversal from 12.)

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.

💡
Try it Yourself First
Though this problem might appear challenging at first, there are systematic ways to approach it. You could think of it as reconstructing a sequence from its fragmented relationships, utilize graph theory to build connections between elements, or simply focus on adjacency to identify the endpoints and traverse the structure. Each method comes with its own trade-offs in terms of implementation clarity, computational efficiency, and how intuitively the solution flows.

Brute Force Approach

Intuition

What is Adjacent Pairs?

The consecutive elements present in array is called Adjacent Pairs.
For example: {1, 2, 3, 4}, here (2, 3), (3, 4) are adjacent pairs. But (1, 3), (2, 4) are not adjacent pairs.

At first glance, the problem of reconstructing an array from adjacent pairs might appear complex. However, upon closer examination, it becomes clear that the problem can be solved as constructing a path in a graph. Each number in the array acts as a node, and the given adjacent pairs represent edges between these nodes.

The key insight here is that the reconstructed array starts and ends at nodes that have only one neighbor (degree 1 in the graph). This property uniquely identifies the endpoints of the array. By leveraging a depth-first search (DFS), we can traverse the graph starting from one endpoint and reconstruct the array by visiting all nodes exactly once.

Approach

Let’s break down the solution into systematic steps and explain how the provided code achieves the reconstruction of the array:

Step 1: Build the Graph
We first create an adjacency list using the given adjacentPairs. This graph will represent the relationships between numbers, where each number is connected to its adjacent numbers in the array.
For each pair [u, v] in adjacentPairs, add v to the adjacency list of u and vice versa. Like, v will store all elements which are adjacent to element u

Step 2: Identify the Starting Point
The array's endpoints are the nodes in the graph with only one neighbor. This is because, in the original array, the first and last numbers each have only one adjacent number. Traverse the adjacency list and find any node with exactly one neighbor. This node will serve as the starting point for our DFS.
Simply those element whose adjacent elements count is equal to 1. That element will be the head or starting point.

Step 3: Traverse the Graph Using DFS
Using DFS, traverse the graph starting from the identified endpoint (or starting point). Keep track of visited nodes to ensure that each node is added to the reconstructed array exactly once. Push each visited node into the result array. At the same time keep track of visited node using visited array (you can make use of unordered_set, set) etc. Recursively explore unvisited neighbors of the current node.
For this we can iterate all childs of each node using for loops and recursively call dfs function considering this child elements as starting point now. Similarly it will happen for other elements as well to get entire elements path in our result array.

Step 4: Return the Result
Once the DFS completes, the result array will contain all the nodes in the order they appear in the original array. Now, lets look at the example below for better understanding.

Example
Input: adjacentPairs = [[2, 1], [3, 4], [3, 2]]
Explanation: Build the Graph
Adjacency list: 
2: [1, 3], 1: [2], 3: [4, 2], 4: [3]
Identify the Starting Point: Nodes with one neighbor: 1 and 4. Choose 1 as the starting point.
Perform DFS: Start at 1: Visit 1 → 2 → 3 → 4.
Reconstructed Array: Result: [1, 2, 3, 4]

Dry Run

Input
adjacentPairs = [[4, -2], [1, 4], [-3, 1]]
Step-by-Step Execution
Build the Graph
-2: [4], 4: [-2, 1], 1: [4, -3], -3: [1]
Identify the Starting Point
Nodes with one neighbor: -2 and -3. Choose -2 as the starting point. (Choosing -3 will also work because ordering of original array doesn’t matter as per question)

Perform DFS
Note: Just to give you example why we can’t start our dfs from any element whose neighbor is not 1
Start at 4: Visit 4 → -2
vis[4] = true, vis[-2] = true (as we visit element we mark/store it)
(stop because we can’t again go to 4, since 4 is already marked visited)
So, we can see that we are not able to get the whole path here.
Start at -2: Visit -2 → 4 → 1 → -3.
Reconstructed Array
Result: [-2, 4, 1, -3]

Code for All Languages
C++ 
class Solution {
public:

    // Depth First Search (DFS) function to traverse the graph and construct the result array
    void dfs(int v, map<int, vector<int>> &adj, unordered_set<int> &vis, vector<int> &ans) {

        // Mark the current node as visited
        vis.insert(v); 
        
        // Add the current node to the result array
        ans.push_back(v); 
        for (auto &x : adj[v]) {
            if (vis.count(x) == 0) { 

                // If the neighbor is not visited, recursively call DFS
                dfs(x, adj, vis, ans);
            }
        }
    }

    // Main function to restore the array from adjacent pairs
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {

        // Adjacency list to store graph connections
        map<int, vector<int>> adj;          

        // Build the adjacency list
        for (auto &v : adjacentPairs) {
            adj[v[0]].push_back(v[1]);
            adj[v[1]].push_back(v[0]);
        }
        
        // Variable to store the starting point of the array
        int head = 0; 
         
        // Find the node with only one neighbor (this is one of the ends of the array)
        for (auto &p : adj) {
            if (p.second.size() == 1) {  
         
                // Endpoints in the array have only one connection       
                head = p.first;
                break;
            }
        }
        
        // To keep track of visited nodes
        unordered_set<int> vis; 
        
        // Result array
        vector<int> ans; 

        // Perform DFS starting from the head
        dfs(head, adj, vis, ans); 

        // Return the reconstructed array 
        return ans; 
    }
};

Java 
import java.util.*;

class Solution {

    // DFS function to traverse the graph and build the result array
    private void dfs(int v, Map<Integer, List<Integer>> adj, Set<Integer> vis, List<Integer> ans) {

        // Mark the current node as visited
        vis.add(v); 

        // Add the current node to the result array
        ans.add(v); 

        // Iterate over neighbors
        for (int x : adj.get(v)) { 

            // If the neighbor is not visited, recursively call DFS
            if (!vis.contains(x)) { 
                dfs(x, adj, vis, ans);
            }
        }
    }

    // Main function to restore the array from adjacent pairs
    public int[] restoreArray(int[][] adjacentPairs) {

        // Adjacency list to store graph connections
        Map<Integer, List<Integer>> adj = new HashMap<>();   
        
        // Build the adjacency list      
        for (int[] pair : adjacentPairs) {
            adj.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            adj.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
        }


        // Variable to store the starting point of the array
        int head = 0;   
       
        // Find the node with only one neighbor (this is one of the ends of the array)
        for (Map.Entry<Integer, List<Integer>> entry : adj.entrySet()) {
           
            // Endpoints in the array have only one connection
            if (entry.getValue().size() == 1) {                  
                head = entry.getKey();
                break;
            }
        }


        // To keep track of visited nodes
        Set<Integer> vis = new HashSet<>();    
        
        // Result list      
        List<Integer> ans = new ArrayList<>();  
        
        // Perform DFS starting from the head        
        dfs(head, adj, vis, ans);  

        // Convert the result list to an array
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

Python 
class Solution:
    # DFS function to traverse the graph and build the result array
    def dfs(self, v, adj, vis, ans):
        
        # Mark the current node as visited
        vis.add(v) 
  
        # Add the current node to the result array
        ans.append(v) 

        # Iterate over neighbors
        for x in adj[v]: 

            # If the neighbor is not visited, recursively call DFS
            if x not in vis:                  
               self.dfs(x, adj, vis, ans)

    # Main function to restore the array from adjacent pairs
    def restoreArray(self, adjacentPairs):
        from collections import defaultdict


        # Adjacency list to store graph connections
        adj = defaultdict(list)     
     
        # Build the adjacency list
        for a, b in adjacentPairs:
            adj[a].append(b)
            adj[b].append(a)

        # Find the node with only one neighbor (this is one of the ends of the array)
        head = next(node for node, neighbors in adj.items() if len(neighbors) == 1)


        # To keep track of visited nodes
        vis = set() 

        # Result array
        ans = [] 
 

        # Perform DFS starting from the head
        self.dfs(head, adj, vis, ans)  

        # Return the reconstructed array
        return ans

Javascript 
class Solution {
    // DFS function to traverse the graph and build the result array
    dfs(v, adj, vis, ans) {

        // Mark the current node as visited
        vis.add(v);

        // Add the current node to the result array
        ans.push(v);
  
        // Iterate over neighbors
        for (const x of adj.get(v)) {

            // If the neighbor is not visited, recursively call DFS
            if (!vis.has(x)) {
                this.dfs(x, adj, vis, ans);
            }
        }
    }

    // Main function to restore the array from adjacent pairs
    restoreArray(adjacentPairs) {

        // Adjacency list to store graph connections
        const adj = new Map();       
  
        // Build the adjacency list
        for (const [a, b] of adjacentPairs) {
            if (!adj.has(a)) adj.set(a, []);
            if (!adj.has(b)) adj.set(b, []);
            adj.get(a).push(b);
            adj.get(b).push(a);
        }

        // Find the node with only one neighbor (this is one of the ends of the array)
        let head = 0;
        for (const [node, neighbors] of adj.entries()) {
            if (neighbors.length === 1) {
                head = node;
                break;
            }
        }


        // To keep track of visited nodes
        const vis = new Set(); 

        // Result array
        const ans = []; 

        // Perform DFS starting from the head
        this.dfs(head, adj, vis, ans); 

        // Return the reconstructed array
        return ans;
    }
}

Time Complexity: O(n)

Net time complexity: 
O(n) ⇒ for storing all elements in map data structure
O(n) ⇒ for iterating over all elements of adj (adjacency array)
O(n) ⇒ for storing all elements in vis array
O(n) ⇒ for running DFS algorithms
So, overall: O(N) + O(N) + O(N) + O(N) ~ O(N)

Space Complexity: O(n)

Auxiliary Space complexity, due to map usage = O(N) [for map data structure storing till n elements]
Similarly, O(N) space required for vis and adj array.
So, all in all total Space complexity = O(N) + O(N) ~ O(N)
Because we are using a map which is adjacency array/matrix for storing all elements and visited array to ignore double calling of dfs from same head.

Optimal Approach

Intuition

The problem is about restoring an array from its adjacent pairs. Each pair gives information about two elements that are adjacent in the original array. The task is to reconstruct the original array from this data.

Key observations:

  • An element at the start or end of the array will appear only once in the adjacent pairs because it only has one neighbor.
  • All other elements (those in the middle of the array) will appear twice in the adjacent pairs since they have two neighbors.
  • This is essentially a graph problem where:
    • Each element is a node.
    • An edge exists between two nodes if they appear in the same pair.
    • The reconstructed array corresponds to a path in this graph.

Approach

To restore the array, we follow these steps:
Step 1: Build an adjacency list
Use the pairs to create a graph in the form of an adjacency list.
For each pair [u, v], add v to the list of neighbors of u and vice versa.

Step 2: Identify the starting node
A node (element) that has only one neighbor in the adjacency list must be at the start or end of the array.
Identify such a node as the starting point (head) of the reconstructed array.

Step 3: Traverse the graph
Use BFS (Breadth-First Search) to traverse the graph starting from the identified head. Keep track of visited nodes to ensure we don’t revisit any element. Add each node to the result array in the order of traversal.

Step 4: Return the result
The BFS traversal order gives the original array, as it ensures all neighbors are visited in sequence.

Examples
Example 1:
Input: [[2, 1], [3, 4], [3, 2]]
Output: [1, 2, 3, 4]
Explanation:
Build adjacency list:
{ 2: [1, 3], 1: [2], 3: [4, 2], 4: [3] }
Node 1 has only one neighbor (2), so it is the starting point.
Traverse the graph: Start with 1 → 2 → 3 → 4.
Result: [1, 2, 3, 4].

Example 2:
Input: [[4, -2], [1, 4], [-3, 1]]
Output: [-2, 4, 1, -3]
Explanation:
Build adjacency list:
{ 4: [-2, 1], -2: [4], 1: [4, -3], -3: [1] }
Node -2 has only one neighbor (4), so it is the starting point.
Traverse the graph: Start with -2 -> 4 -> 1 -> -3.
Result: [-2, 4, 1, -3].

Dry Run

Input: [[2, 1], [3, 4], [3, 2]]
Step 1: Build adjacency list
For pair [2, 1]: adj[2] = [1], adj[1] = [2]
For pair [3, 4]: adj[3] = [4], adj[4] = [3]
For pair [3, 2]: adj[3] = [4, 2], adj[2] = [1, 3]
Final adjacency list: { 2: [1, 3], 1: [2], 3: [4, 2], 4: [3] }

Step 2: Identify starting node
Node 1 has only one neighbor (2), so it is the starting point.

Step 3: BFS traversal
Initialize head = 1, vis = {}, ans = [].
Push 1 to the queue and mark it as visited.
Queue: [1], ans = [1]

Process node 1:
Pop 1. Neighbors are [2].
Visit 2, mark it as visited, and push to queue.
Queue: [2]
ans = [1, 2]

Process node 2:
Pop 2. Neighbors are [1, 3].
1 is already visited. Visit 3, mark it as visited, and push to queue.
Queue: [3]
ans = [1, 2, 3]

Process node 3:
Pop 3. Neighbors are [4, 2].
2 is already visited. Visit 4, mark it as visited, and push to queue.
Queue: [4]
ans = [1, 2, 3, 4]

Process node 4:
Pop 4. Neighbors are [3].
3 is already visited.
Queue becomes empty.

Step 4: Return the result
Final ans = [1, 2, 3, 4].
Output: [1, 2, 3, 4]

Code for All Languages
C++ 
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        // adjacency list created to traversal in graph using BFS
        map<int, vector<int>> adj;

        // to track marked elements as visited
        unordered_set<int> vis;

        // checking which element has only one child or connected to just on element
        for(auto &v : adjacentPairs) {

            // getting all connections to adjacency list graph format
            int u = v[0], v1 = v[1];
            adj[u].push_back(v1);
            adj[v1].push_back(u);
        }

        // marking head as -1 currently becoz we don't know right now.
        int head = -1;

        // iterate over all adjacency lists to find which parent has only one child
        for(auto &p : adj){
            auto vec = p.second;

            // once we find it, we store that parent to head and break the loop
            if(vec.size() == 1){
                head = p.first;
                break;
            }
        }

        // From here begins the BFS (Breadth First Search) code
        vector<int> ans;

        // we first mark that parent as visited
        vis.insert(head);

        // we store parent elements in queue Data structure
        queue<int> q;

        // store the head to look for all its child whether its a part of the path
        q.push(head);
        ans.push_back(head);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            auto vec = adj[u];
            for(int &x : vec){
                if(!vis.count(x)){
                    // if x is not visited then fire all surrounding elements and first mark it as visited
                    vis.insert(x); 
                    ans.push_back(x);
                    q.push(x);
                }
            }
        }
        // returns our answer
        return ans;
    }
};

Java 
import java.util.*;

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        // adjacency list created to traversal in graph using BFS
        Map<Integer, List<Integer>> adj = new HashMap<>();

        // to track marked elements as visited
        Set<Integer> vis = new HashSet<>();

        // checking which element has only one child or connected to just one element
        for (int[] v : adjacentPairs) {
            // getting all connections to adjacency list graph format
            int u = v[0], v1 = v[1];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v1);
            adj.computeIfAbsent(v1, k -> new ArrayList<>()).add(u);
        }

        // marking head as -1 currently because we don't know right now.
        int head = -1;

        // iterate over all adjacency lists to find which parent has only one child
        for (Map.Entry<Integer, List<Integer>> p : adj.entrySet()) {
            List<Integer> vec = p.getValue();

            // once we find it, we store that parent to head and break the loop
            if (vec.size() == 1) {
                head = p.getKey();
                break;
            }
        }

        // From here begins the BFS (Breadth First Search) code
        List<Integer> ans = new ArrayList<>();

        // we first mark that parent as visited
        vis.add(head);

        // we store parent elements in queue Data structure
        Queue<Integer> q = new LinkedList<>();

        // store the head to look for all its child whether it's a part of the path
        q.offer(head);
        ans.add(head);
        while (!q.isEmpty()) {
            int u = q.poll();
            List<Integer> vec = adj.get(u);
            for (int x : vec) {
                if (!vis.contains(x)) {
                    // if x is not visited then fire all surrounding elements and first mark it as visited
                    vis.add(x);
                    ans.add(x);
                    q.offer(x);
                }
            }
        }
        // returns our answer
        return ans.stream().mapToInt(i -> i).toArray();
    }
}

Python 
from collections import defaultdict, deque

class Solution:
    def restoreArray(self, adjacentPairs):
        # adjacency list created to traversal in graph using BFS
        adj = defaultdict(list)

        # to track marked elements as visited
        vis = set()

        # checking which element has only one child or connected to just one element
        for u, v1 in adjacentPairs:
            # getting all connections to adjacency list graph format
            adj[u].append(v1)
            adj[v1].append(u)

        # marking head as -1 currently because we don't know right now.
        head = -1

        # iterate over all adjacency lists to find which parent has only one child
        for key, vec in adj.items():
            # once we find it, we store that parent to head and break the loop
            if len(vec) == 1:
                head = key
                break

        # From here begins the BFS (Breadth First Search) code
        ans = []

        # we first mark that parent as visited
        vis.add(head)

        # we store parent elements in queue Data structure
        q = deque()

        # store the head to look for all its child whether it's a part of the path
        q.append(head)
        ans.append(head)
        while q:
            u = q.popleft()
            vec = adj[u]
            for x in vec:
                if x not in vis:
                    # if x is not visited then fire all surrounding elements and first mark it as visited
                    vis.add(x)
                    ans.append(x)
                    q.append(x)

        # returns our answer
        return ans

Javascript 
class Solution {
    restoreArray(adjacentPairs) {
        // adjacency list created to traversal in graph using BFS
        const adj = new Map();

        // to track marked elements as visited
        const vis = new Set();

        // checking which element has only one child or connected to just one element
        for (const [u, v1] of adjacentPairs) {
            // getting all connections to adjacency list graph format
            if (!adj.has(u)) adj.set(u, []);
            if (!adj.has(v1)) adj.set(v1, []);
            adj.get(u).push(v1);
            adj.get(v1).push(u);
        }

        // marking head as -1 currently because we don't know right now.
        let head = -1;

        // iterate over all adjacency lists to find which parent has only one child
        for (const [key, vec] of adj.entries()) {
            // once we find it, we store that parent to head and break the loop
            if (vec.length === 1) {
                head = key;
                break;
            }
        }

        // From here begins the BFS (Breadth First Search) code
        const ans = [];

        // we first mark that parent as visited
        vis.add(head);

        // we store parent elements in queue Data structure
        const q = [];

        // store the head to look for all its child whether it's a part of the path
        q.push(head);
        ans.push(head);
        while (q.length > 0) {
            const u = q.shift();
            const vec = adj.get(u);
            for (const x of vec) {
                if (!vis.has(x)) {
                    // if x is not visited then fire all surrounding elements and first mark it as visited
                    vis.add(x);
                    ans.push(x);
                    q.push(x);
                }
            }
        }

        // returns our answer
        return ans;
    }
}

Time Complexity: O(n)

1. Building the adjacency list
For each pair in adjacentPairs size = m (no. of pairs), we perform constant-time operations to add the elements to the adjacency list.

  • Using a hash map, the insertion and access operations are O(1).
  • Total time: O(m)

2. Identifying the starting node

  • We iterate through the adjacency list. For each node, we check the size of its adjacency list (its degree).
  • There are (n) nodes in the adjacency list, and checking the degree of a node takes O(1).
  • Total time: O(n).

3. BFS traversal

  • BFS visits each node exactly once and processes all of its neighbors.
  • Each edge (pair) is traversed twice (once for each endpoint), so the total edge processing is O(2m)
  • Total time for BFS: O(n)

Total Time Complexity
Adding up all components:

  • O(m) + O(n) + O(m) = O(n) + O(n) + O(n) = O(n).
    Thus, the time complexity is O(n).

Space Complexity: O(n)

1. Adjacency list
We store the adjacency list as a hash map where each key corresponds to a node, and the value is a list of its neighbors.
Since there are (n) nodes and (m) edges, the adjacency list takes O(n + m) space.
With (m = n - 1), this becomes O(n + (n - 1)) = O(2n - 1) = O(n).

2. Visited set
We use a set to keep track of visited nodes during the BFS traversal.
In the worst case, all (n) nodes are visited.
Space required: O(n).

3. BFS queue
The BFS queue stores nodes that are waiting to be processed. In the worst case, it can contain all (n) nodes (when all nodes are added before processing starts).
Space required: O(n).

4. Result array
The result array stores the restored array of size (n).
Space required: O(n).
Total Space Complexity
Adding up all components: O(n) + O(n) + O(n) + O(n) = 4O(n) = O(n) .
Thus, the space complexity is O(n).
Note: In this approach we don't have an extra O(n) stack space due to recursion like we had in our earlier Brute force approach. So, this approach is slightly better on using BFS traversal.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to] reconstruct the itinerary in order. This problem involves reconstructing a sequence based on adjacency pairs, similar to restoring an array from adjacent pairs.

Course Schedule II

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. This problem involves reconstructing a sequence (course order) based on adjacency-like relationships (prerequisites), which is conceptually similar to restoring an array from adjacent pairs.