Restore the Array From Adjacent Pairs

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] = [u_i, v_i] indicates that the elements u_i and v_i 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. Here are some examples:

1. adjacentPairs = [[2,1],[3,4],[3,2]]. The output should be [1,2,3,4].
2. adjacentPairs = [[4,-2],[1,4],[-3,1]]. The output should be [-2,4,1,-3].
3. adjacentPairs = [[100000,-100000]]. The output should be [100000,-100000].

Can you write an algorithm for this problem?

def restore_array(adjacentPairs):
    """
    Given an array of adjacent pairs, reconstruct the original array.

    Args:
        adjacentPairs (List[List[int]]): A list of adjacent pairs.

    Returns:
        List[int]: The reconstructed array.
    """
    graph = {}
    degrees = {}
    for u, v in adjacentPairs:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)
        degrees[u] = degrees.get(u, 0) + 1
        degrees[v] = degrees.get(v, 0) + 1

    start_node = None
    for node, degree in degrees.items():
        if degree == 1:
            start_node = node
            break

    result = []
    visited = {start_node}
    
    def dfs(node):
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor)

    dfs(start_node)
    return result

# Example Usage:
# adjacentPairs = [[2,1],[3,4],[3,2]]
# print(restore_array(adjacentPairs)) # Output: [1, 2, 3, 4] or equivalent

# adjacentPairs = [[4,-2],[1,4],[-3,1]]
# print(restore_array(adjacentPairs)) # Output: [-2, 4, 1, -3] or equivalent

# adjacentPairs = [[100000,-100000]]
# print(restore_array(adjacentPairs)) # Output: [100000, -100000]

Explanation:

1. Build the Graph:

   • Create a graph (dictionary) where keys are numbers from nums, and values are lists of their adjacent numbers.
   • Also create a degrees dictionary to store the degree of each node, representing the number of adjacent nodes it has.

2. Find the Start Node:

   • The start node is the one with a degree of 1 (i.e., only one adjacent number), as it's one of the ends of the array.

3. Depth-First Search (DFS):

   • Start a DFS from the start_node.
   • Append each visited node to the result list.
   • For each neighbor of the current node, if it hasn't been visited, recursively call DFS on it.

4. Return the Result:

   • The result list now contains the reconstructed array.

Big(O) Run-time Analysis:

• O(n), where n is the number of elements in the array. This is because we iterate through the adjacentPairs once to build the graph, and then we perform a DFS that visits each node once.

Big(O) Space Usage Analysis:

• O(n), where n is the number of elements in the array. This is because the graph and the visited set can store up to n elements in the worst case.

Edge Cases:

• Empty Input: If adjacentPairs is empty, return an empty array.
• Single Pair: If adjacentPairs contains only one pair, return the array containing that pair's elements.
• Negative Numbers: The code handles negative numbers correctly as they are used as keys in the graph.
• Multiple Solutions: The problem statement allows returning any valid solution, and the DFS approach naturally returns one of the possible solutions.
• Disconnected graph: The problem guarantees that there exists some nums that has adjacentPairs as its pairs. Therefore, it is guaranteed to be a connected graph and we don't need to handle disconnected components. If the question were to NOT provide such a guarantee, we would need to loop through each discovered disconnected component and perform DFS on each to recover the full array.