We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sequence Reconstruction

Number: 444

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a permutation array nums and a list of subsequences, sequences, determine if nums is the only shortest supersequence that contains every sequence in sequences as a subsequence. In other words, by using the ordering constraints from each subsequence, check if there exists exactly one way (that equals nums) to reconstruct the full sequence using the minimum number of elements.

Key Insights

  • The problem requires reconstructing the sequence using ordering constraints, making it natural to use topological sorting.
  • Build a directed graph where an edge u -> v signifies that u comes before v.
  • Count indegrees for each node; nodes with zero indegree are eligible to appear next in the sequence.
  • The reconstruction is unique if at every step there is exactly one candidate with indegree 0.
  • Finally, ensure the reconstructed order exactly matches nums.

Space and Time Complexity

Time Complexity: O(N + M), where N is the number of elements in nums and M is the total number of elements in sequences. Space Complexity: O(N + M) due to the graph, indegree array/map, and auxiliary data structures.

Solution

The solution uses a graph-based approach, specifically employing topological sort to determine the order of nodes. First, construct a graph and compute indegree counts by iterating through each subsequence in sequences. Then, perform a topological sort: add nodes with indegree 0 to a queue and process them one by one. If at any point more than one node is available (queue size greater than one), the reconstruction is not unique so return false. Additionally, as you pop each node, verify that it coincides with the corresponding element in the given nums. If the complete reconstructed order matches nums and no ambiguities were encountered during the sort, return true. Otherwise, return false.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

def sequenceReconstruction(nums, sequences):
    from collections import defaultdict, deque

    n = len(nums)
    # Initialize graph and indegree for each node in the permutation
    graph = defaultdict(set)  # Graph represented as a dictionary mapping node to a set of neighbor nodes
    indegree = {i: 0 for i in range(1, n + 1)}  # Indegree dictionary for nodes

    # Build graph and compute indegree counts based on the sequences constraints
    for seq in sequences:
        for i in range(len(seq) - 1):
            u, v = seq[i], seq[i + 1]
            if v not in graph[u]:
                graph[u].add(v)
                indegree[v] += 1

    # Use deque for topological sorting
    queue = deque([node for node in indegree if indegree[node] == 0])
    reconstruction = []

    while queue:
        # If more than one candidate is available, the order is not unique
        if len(queue) > 1:
            return False
        current = queue.popleft()
        reconstruction.append(current)
        # Check if the current element matches the corresponding element in nums
        if reconstruction[-1] != nums[len(reconstruction) - 1]:
            return False
        # Decrease the indegree of neighbors and add them to the queue if indegree becomes 0
        for neighbor in graph[current]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return reconstruction == nums

# Example usage:
if __name__ == '__main__':
    nums = [1, 2, 3]
    sequences = [[1, 2], [1, 3], [2, 3]]
    print(sequenceReconstruction(nums, sequences))  # Expected output: True
← Back to All Questions