Watch 10 video solutions for Restore the Array From Adjacent Pairs, a medium level problem involving Array, Hash Table, Depth-First Search. This walkthrough by codestorywithMIK has 7,176 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |