Skip to main content

Sequence Reconstruction

Question​

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]

Solution​

all//Sequence Reconstruction.py


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
    visited.add(num)

    # add the node to the result list
    result.append(num)

    # 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