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 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.
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.
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. |
Leetcode 1743. Restore the Array From Adjacent Pairs • Fraz • 6,430 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 FleetCodePractice this problem
Open in Editor