Restore The Array From Adjacent Pairs - Leetcode Solution

The problem "Restore The Array From Adjacent Pairs" on LeetCode can be solved using Graph Theory and Depth-First Search Algorithm.

Problem Description:

You are given an array of n unique integers, where each element of the array is adjacent to exactly one other element. Your task is to restore the original array from the given adjacent pairs. You can assume that there is a unique solution for the given input array.

Algorithm:

1. Create a dictionary to store the adjacent pairs.
2. Traverse through the given array and add the adjacent pairs as keys and values in the dictionary.
3. Create a visited set to keep track of the nodes that have already been visited.
4. Create a function dfs to perform depth-first search.
5. In dfs, start with a given node and add it to the visited set.
6. Check the number of adjacent nodes of the current node.
7. If there is only one adjacent node, add it to the answer array and call the dfs function recursively with the adjacent node.
8. If there are two adjacent nodes, choose one of them that has not been visited yet.
9. Repeat steps 7-8 until all nodes have been visited.

Python Code:

Here is the Python code to implement the above algorithm:

class Solution: def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]: adj = {} for a, b in adjacentPairs: if a not in adj: adj[a] = [] if b not in adj: adj[b] = [] adj[a].append(b) adj[b].append(a)

    visited = set()
    ans = []
    def dfs(u):
        visited.add(u)
        ans.append(u)
        for v in adj[u]:
            if v not in visited:
                dfs(v)

    start = None
    for u in adj:
        if len(adj[u]) == 1:
            start = u
            break

    dfs(start)
    return ans

Time Complexity: O(n), where n is the number of elements in the array.

Space Complexity: O(n), where n is the number of elements in the array.

1