Restore the Array From Adjacent Pairs — LeetCode 1743 Python Solution

The problem

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.

Example

Input

adjacentPairs = [[2,1],[3,4],[3,2]]

Output

[1,2,3,4]

Explanation

This array has all its adjacent pairs in adjacentPairs.

Python solution

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        for a, b in adjacentPairs:
            g[a].append(b)
            g[b].append(a)
        n = len(adjacentPairs) + 1
        ans = [0] * n
        for i, v in g.items():
            if len(v) == 1:
                ans[0] = i
                ans[1] = v[0]
                break
        for i in range(2, n):
            v = g[ans[i - 1]]
            ans[i] = v[0] if v[1] == ans[i - 2] else v[1]
        return ans

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1743. Restore the Array From Adjacent Pairs is filed here because LeetCode tags it Depth-First Search, which is the vocabulary this hub collects.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems