Restore the Array From Adjacent Pairs (Leetcode 1743)

Problem Link: https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/

from collections import defaultdict
class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        
        
#         def dfs(i):
            
#             if(i not in vis):
#                 vis.add(i)
#                 ans.append(i)
#                 # print(i)
#                 for adjnode in adj[i]:
#                     if(adjnode not in vis):
#                         dfs(adjnode)
        
        adj=defaultdict(list)
        for i in adjacentPairs:
            adj[i[0]].append(i[1])
            adj[i[1]].append(i[0])
        
        # Using a visited array
        # gave me TLE
        # So,strictly use set
        vis=set()
        ans=[]
        for i in adj:
            if(len(adj[i])==1):
                head=i
                break
        q=[head]
        vis.add(head)
        while(len(q)>0):
            
            for _ in range(len(q)):
                
                curr=q.pop()
                ans.append(curr)
                
                for adjnode in adj[curr]:
                    if(adjnode not in vis):
                        q.insert(0,adjnode)
                        vis.add(adjnode)
        return ans

Last updated