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.Problem Overview: You receive adjacentPairs, where each pair represents two neighboring elements in an unknown array. The task is to reconstruct the original array. Every element appears in at most two pairs, which means the structure naturally forms a linear chain when modeled as a graph.
Approach 1: Graph Construction and Traversal (O(n) time, O(n) space)
Treat each number as a node and each adjacent pair as an undirected edge. Build an adjacency list using a hash table where each value maps to its neighbors. In the reconstructed array, the two endpoints appear only once in the pairs, so their adjacency list has size 1. Start from any endpoint, then repeatedly move to the neighbor that has not been visited yet.
This becomes a simple path traversal problem on a graph with maximum degree 2. Maintain a visited set or track the previous element to avoid going backward. You can implement the traversal iteratively or with depth-first search. Since every element is processed once, the algorithm runs in O(n) time with O(n) space for the adjacency structure.
This approach works because the graph is guaranteed to form a single chain rather than multiple branches. Endpoints anchor the reconstruction, and each step reveals the next element in the sequence.
Approach 2: Graph Construction and Ordering with Sorting (O(n log n) time, O(n) space)
Another option is to first construct the same adjacency list, then order elements based on traversal rules while maintaining a structure that determines the next node deterministically. Some implementations sort adjacency lists so the traversal always chooses neighbors in a consistent order.
After identifying an endpoint (degree 1 node), iterate through neighbors and append them to the result array while marking visited elements. Sorting adds overhead but simplifies deterministic ordering logic in some languages such as C#. The reconstruction still follows the single-chain property of the graph.
This version has O(n log n) time complexity due to sorting operations and O(n) extra space for the graph and visited tracking.
Recommended for interviews: The graph construction and traversal approach is what interviewers expect. Modeling the problem as a path in a graph shows strong understanding of array relationships and adjacency structures. Identifying endpoints and performing a linear traversal achieves the optimal O(n) time complexity, which demonstrates algorithmic efficiency.
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.
This 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.
Python
Java
C++
JavaScript
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.
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.
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.
C#
Time Complexity: O(n). Space Complexity: O(n), for maintaining necessary data structures.
| Approach | Complexity |
|---|---|
| Graph Construction and Traversal | Time Complexity: O(n), where n is the number of elements in nums. |
| Graph Construction and Sorting | Time Complexity: O(n). Space Complexity: O(n), for maintaining necessary data structures. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Construction and Traversal | O(n) | O(n) | Best general solution. Linear traversal from endpoint using adjacency list. |
| Graph Construction with Sorting | O(n log n) | O(n) | Useful when deterministic neighbor ordering is needed or when implementation favors sorted adjacency lists. |
Restore the Array From Adjacent Pairs | Easy Explanation | Dry Run | Intuition | Leetcode-1743 • codestorywithMIK • 7,176 views views
Watch 9 more video solutions →Practice Restore the Array From Adjacent Pairs with our built-in code editor and test cases.
Practice on FleetCode