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 == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 105-105 <= nums[i], ui, vi <= 105nums that has adjacentPairs as its pairs.In #1743 Restore the Array From Adjacent Pairs, the key idea is to observe that each pair represents an undirected connection between two numbers. This naturally forms a graph where each value is a node and adjacent pairs create edges. Since the original array is a single valid sequence, the graph will resemble a path.
Start by building an adjacency list using a HashMap that maps each number to its neighbors. In a valid path, the two ends of the array will have only one neighbor, while all other elements will have two. By identifying an endpoint, you can reconstruct the array by performing a DFS or iterative traversal through neighbors while avoiding revisiting the previous element.
This approach efficiently rebuilds the sequence by following the path structure of the graph. Because each pair and node is processed once, the solution runs in linear time with additional space for the adjacency structure.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Graph Traversal (DFS/Iterative) | O(n) | O(n) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
Find the first element of nums - it will only appear once in adjacentPairs.
The adjacent pairs are like edges of a graph. Perform a depth-first search from the first element.
In this approach, we will treat the problem as one of finding a path in a graph. Each element in the array is a node, and each adjacent pair represents an edge connecting two nodes. We can represent this graph using an adjacency list.
First, build the adjacency list from the given pairs. Elements with degree 1 (i.e., nodes with only one neighbor) are potential starting or ending points for the original array. We pick one such node and perform a depth-first search (DFS) or breadth-first search (BFS) to reconstruct the array.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(n), for storing the adjacency list and visited set.
1from collections import defaultdict
2
3def restoreArray(adjacentPairs):
4 adj_map = defaultdict(list)
5 for u, v in adjacentPairs:
6 adj_map[u].append(v)
7 adj_map[v].append(u)
8
9 # Find a starting point (it should have a single connection)
10 start = next(k for k, v in adj_map.items() if len(v) == 1)
11
12 # Restore the array by traversing
13 res = []
14 visited = set()
15 current = start
16 prev = None
17 while current is not None:
18 res.append(current)
19 visited.add(current)
20 neighbors = adj_map[current]
21 next_node = next((n for n in neighbors if n != prev), None)
22 prev = current
23 current = next_node
24
25 return res
26This Python solution constructs an adjacency list using defaultdict from the collections module. It picks a starting node with a single connection, then performs a traversal using a while loop to reconstruct the array. Nodes are marked as visited to avoid revisiting.
This approach builds the adjacency list similar to the previous one but uses sorting to aid in selecting the next node. While sorting might not always be the primary mechanism to solve the problem, it ensures adjacent nodes can be identified quickly, which helps in managing which node to process next in the construction of the resultant array.
Time Complexity: O(n). Space Complexity: O(n), for maintaining necessary data structures.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] RestoreArray(int[][] adjacentPairs) {
6 var adjMap = new Dictionary<int, List<int>>();
7
// Build the adjacency map
foreach (var pair in adjacentPairs) {
if (!adjMap.ContainsKey(pair[0])) adjMap[pair[0]] = new List<int>();
if (!adjMap.ContainsKey(pair[1])) adjMap[pair[1]] = new List<int>();
adjMap[pair[0]].Add(pair[1]);
adjMap[pair[1]].Add(pair[0]);
}
// Find the start of the array
int start = 0;
foreach (var kvp in adjMap) {
if (kvp.Value.Count == 1) {
start = kvp.Key;
break;
}
}
// Reconstruct the array
List<int> result = new List<int>();
HashSet<int> visited = new HashSet<int>();
int prev = -1;
while (true) {
result.Add(start);
visited.Add(start);
var neighbors = adjMap[start];
int next = -1;
foreach (var neighbor in neighbors) {
if (neighbor != prev && !visited.Contains(neighbor)) {
next = neighbor;
break;
}
}
if (next == -1) break;
prev = start;
start = next;
}
return result.ToArray();
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In the original array, elements in the middle appear in two adjacent pairs, giving them two neighbors. The first and last elements only appear in one pair each, so they have exactly one neighbor in the adjacency structure.
Yes, graph reconstruction and adjacency-based traversal problems like this are common in technical interviews. Companies often test understanding of hash maps, graph modeling, and traversal techniques such as DFS or BFS.
A hash map (or dictionary) is the most useful data structure for this problem. It stores each number and its neighboring elements, effectively creating an adjacency list representation of the graph formed by the pairs.
The optimal approach models the problem as a graph. Use a hash map to build an adjacency list from the pairs, identify an endpoint with only one neighbor, and traverse the graph to reconstruct the array. This ensures linear time reconstruction.
The C# solution is similar in spirit to the earlier ones. It builds a dictionary for adjacency mapping and rebuilds the array by picking nodes not yet visited. It emphasizes cleanliness and direct approach instead of relying on complex loops or conditional checks.