Skip to main content

Sequence Reconstruction


Given a sequence of n integers arr, determine whether it is possible to reconstruct the sequence from the given sequence.

Example 1
Input: org = [1,2,3], seqs = [[1,2],[1,3]]

Output: [1,2,3]



def sequenceReconstruction(originalSeq, sequences):
# create a graph with the original sequence
graph = {num: [] for num in originalSeq}

# add edges to the graph based on the sequences
for seq in sequences:
for i in range(len(seq) - 1):
graph[seq[i]].append(seq[i + 1])

# create a set to store visited elements
visited = set()

# create a list to store the result
result = []

# iterate over the original sequence
for num in originalSeq:
# check if the element has been visited
if num not in visited:
# if not, then use a dfs to traverse the graph
if not dfs(graph, num, visited, result):
return []

# if the length of the result is not equal to the original sequence, return empty list
return result if len(result) == len(originalSeq) else []

def dfs(graph, num, visited, result):
# mark the node as visited

# add the node to the result list

# iterate over the neighbors
for neighbor in graph[num]:
# if the neighbor has been visited, return False
if neighbor in visited:
return False

# if not, then traverse the graph
if not dfs(graph, neighbor, visited, result):
return False

# return True if all the neighbors have been traversed
return True