Solution Explanation for Restoring an Array from Adjacent Pairs

This problem involves reconstructing an integer array from a list of its adjacent pairs. The input adjacentPairs is a 2D array where each inner array represents a pair of adjacent numbers in the original array. The challenge is that the order within each pair and the overall order of the pairs are not guaranteed.

Approach:

Both solutions leverage the concept of a graph. We can represent the input pairs as edges in an undirected graph where each unique integer is a node. The degree (number of edges connected to a node) of each node in this graph is crucial.

Solution 1: Iterative Approach

1. Graph Construction: First, we build an adjacency list representation of the graph using a HashMap (or defaultdict in Python). Each key in the map represents a node (integer), and the value is a list of its neighbors.

2. Finding the Start Node: Crucially, the endpoints of the original array will have a degree of 1 (only one adjacent element). We iterate through the graph to identify a node with a degree of 1; this will be our starting point for reconstructing the array.

3. Iterative Reconstruction: Starting from the identified node, we iteratively build the array. In each step:

   • We add the current node to the ans array.
   • We find the next node by looking at the neighbors of the current node. Since we know the previous node, we can easily identify the next node from the neighbor list.

4. Return the Array: Finally, we return the ans array, which now contains the reconstructed integer array.

Solution 2: Depth-First Search (DFS) Approach

1. Graph Construction: Similar to Solution 1, we create an adjacency list graph representing the adjacent pairs.

2. Finding the Start Node: We locate a node with a degree of 1 – this serves as the root of our DFS traversal.

3. DFS Traversal: We perform a depth-first search starting from the identified root node. The DFS recursively explores the graph, adding each visited node to the ans array. The key is to maintain a fa (parent) variable to avoid cycles and ensure that we only traverse to unvisited adjacent nodes.

4. Return the Array: The ans array, built during the DFS traversal, represents the reconstructed integer array.

Time Complexity Analysis:

• Solution 1 (Iterative): O(N), where N is the number of elements in the original array. We iterate through the graph (adjacency list) once to find the starting node and then iterate once more to reconstruct the array. All other operations are O(1) on average.

• Solution 2 (DFS): O(N). The DFS traversal visits each node and edge exactly once. Building the graph is also O(N).

Space Complexity Analysis:

• Solution 1 (Iterative): O(N) to store the adjacency list graph and the output array.

• Solution 2 (DFS): O(N) to store the adjacency list graph and the recursion stack during the DFS traversal (in the worst-case scenario, the depth of the recursion could be N).

Code Examples (Python):

(Solution 1)

from collections import defaultdict
 
class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for u, v in adjacentPairs:
            graph[u].append(v)
            graph[v].append(u)
 
        start_node = next(node for node, neighbors in graph.items() if len(neighbors) == 1)
        result = [start_node]
        prev_node = start_node
        
        for _ in range(len(adjacentPairs)):
            next_node = next(neighbor for neighbor in graph[prev_node] if neighbor != result[-2])
            result.append(next_node)
            prev_node = next_node
 
        return result
 

(Solution 2)

from collections import defaultdict
 
class Solution:
    def restoreArray(self, adjacentPairs):
        graph = defaultdict(list)
        for u, v in adjacentPairs:
            graph[u].append(v)
            graph[v].append(u)
 
        start_node = next(node for node, neighbors in graph.items() if len(neighbors) == 1)
        result = []
 
        def dfs(node, parent):
            result.append(node)
            for neighbor in graph[node]:
                if neighbor != parent:
                    dfs(neighbor, node)
 
        dfs(start_node, -1) #-1 indicates no parent for the root.
        return result

Both solutions provide efficient ways to solve this problem. The iterative approach might be slightly faster in practice due to the overhead of recursive calls in DFS, but the difference is often negligible for reasonably sized inputs. Choose the solution you find more readable and maintainable.