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