Restore the Array From Adjacent Pairs
Medium
You are given a 2D integer array adjacentPairs representing pairs of adjacent elements from a forgotten array nums. The nums array had n unique elements. Your task is to reconstruct and return the original nums array. Each adjacentPairs[i] = [u_i, v_i] indicates that elements u_i and v_i were adjacent in nums. The order of pairs in adjacentPairs is arbitrary, and each adjacent pair nums[i] and nums[i+1] exists in adjacentPairs as either [nums[i], nums[i+1]] or [nums[i+1], nums[i]].
Example 1:
Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: The array [1, 2, 3, 4] has all its adjacent pairs in adjacentPairs.
Example 2:
Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: The array [-2, 4, 1, -3] satisfies the condition.
Another valid output is [-3,1,4,-2].
Example 3:
Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]
Constraints:
2 <= n <= 10^5-10^5 <= nums[i], u_i, v_i <= 10^5- There exists at least one nums that has
adjacentPairsas its pairs.
Write a function that takes the adjacentPairs array as input and returns the reconstructed nums array. Discuss the time and space complexity of your solution. Consider edge cases such as when the input array is empty or contains only one pair.
Solution
Brute Force Solution
A brute force approach would involve trying every possible permutation of the numbers present in the adjacentPairs array. We can construct all possible permutations and check if each adjacent pair exists within the given adjacentPairs. This approach is highly inefficient.
Big O Runtime
O(n!), where n is the number of elements, due to generating all possible permutations.
Big O Space
O(n), where n is the number of elements, to store the current permutation.
Optimal Solution
A more efficient approach involves constructing a graph from the adjacentPairs array, where each number is a node and each pair represents an edge. We can then find the start node (which has only one adjacent node) and traverse the graph to reconstruct the original array.
Here's a breakdown of the optimal solution:
- Build the Graph: Create an adjacency list (or a hash map) to represent the graph. For each pair
[u, v]inadjacentPairs, addvto the adjacency list ofu, anduto the adjacency list ofv. - Find the Start Node: Iterate through the graph to find a node that has only one neighbor. This will be one of the end points of the original array.
- Traverse the Graph: Starting from the start node, traverse the graph using Depth-First Search (DFS). Keep track of the visited nodes to avoid cycles. The order in which we visit the nodes will be the original array.
Edge Cases
- Empty Input: If
adjacentPairsis empty, return an empty array. - Single Pair: If
adjacentPairscontains only one pair, the array is simply the pair itself. - Negative Numbers: The algorithm should work correctly with negative numbers.
- Duplicate Pairs: The problem statement guarantees unique elements. However, if duplicate pairs exist, the graph construction should handle them correctly (e.g., by using a set in the adjacency list).
Big O Runtime
O(n), where n is the number of elements. Building the graph takes O(n) time, finding the start node takes O(n) time, and traversing the graph using DFS takes O(n) time.
Big O Space
O(n), where n is the number of elements. We need to store the graph (adjacency list) and the result array, each requiring O(n) space.
Code (Python)
from collections import defaultdict
def restoreArray(adjacentPairs):
graph = defaultdict(list)
for u, v in adjacentPairs:
graph[u].append(v)
graph[v].append(u)
start_node = None
for node, neighbors in graph.items():
if len(neighbors) == 1:
start_node = node
break
result = []
visited = set()
def dfs(node):
result.append(node)
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
dfs(start_node)
return result
