Sequence Reconstruction

Medium

Asked by:

41 views

Topics:

GraphsArrays

You are given an integer array nums of length n where nums is a permutation of the integers in the range [1, n]. You are also given a 2D integer array sequences where sequences[i] is a subsequence of nums.

Check if nums is the shortest possible and lexicographically smallest supersequence of all the sequences in sequences. If it is, return true. Otherwise, return false.

A sequence x is a supersequence of a sequence y if all elements of y appear in x in the same order.

So for example, [1,3,4] is a supersequence of [1,3] and [3,4], and [1,3,5,2,4] is a supersequence of [1,3,2,4].

Example 1:

Input: nums = [1,2,3], sequences = [[1,2],[1,3]]
Output: true
Explanation: The sequences [1,2] and [1,3] can uniquely reconstruct the original sequence [1,2,3].

Example 2:

Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
Output: false
Explanation: The sequences [1,2], [1,3], and [2,3] can reconstruct the original sequence [1,2,3] as well as the sequence [1,3,2].

Example 3:

Input: nums = [1,2,3], sequences = [[1,2]]
Output: false
Explanation: The given sequence [1,2] is not sufficient to reconstruct the original sequence [1,2,3].

Constraints:

n == nums.length
1 <= n <= 10⁴
nums is a permutation of the integers in the range [1, n].
1 <= sequences.length <= 10⁴
1 <= sequences[i].length <= 10⁴
1 <= sum(sequences[i].length) <= 10⁵
1 <= sequences[i][j] <= n
All the values of sequences[i] are distinct.
Every element of nums is in at least one sequence in sequences.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the sequences in `sequences` contain duplicate numbers, and if so, how should they be handled in the reconstruction?
If the original sequence cannot be uniquely reconstructed from the given `sequences`, what should I return? (e.g., null, empty sequence, or an error indication)?
What is the range of integer values that might appear in the sequences and the original sequence?
Is the input `sequences` guaranteed to be non-empty, and what should I do if it's empty?
Are the integers in the `sequences` guaranteed to be a subset of the integers in the original sequence, or is it possible to have integers that don't belong to the original sequence (and if so, how do I determine the valid range of integers)?

Brute Force Solution

Approach

The brute force approach to sequence reconstruction involves checking every single possible combination of ordered elements to see if it matches the original sequence. It's like trying every possible arrangement, one by one, until we find the right one, or determine that it's impossible. This method guarantees finding a solution if one exists, but it can be very slow.

Here's how the algorithm would work step-by-step:

Consider all possible orderings of the elements provided in the smaller sequences.
For each possible ordering, compare it to the original sequence to see if it's a valid reconstruction.
A valid reconstruction means that the ordering of the smaller sequences preserves the order of the elements in the original sequence.
If any of these orderings perfectly match the original sequence, then we have successfully reconstructed it.
If we have tested every possible ordering and none match, the original sequence cannot be reconstructed from the given smaller sequences.

Code Implementation

from itertools import permutations

def sequence_reconstruction_brute_force(original_sequence, sequences):
    all_elements = set()
    for sequence in sequences:
        for element in sequence:
            all_elements.add(element)

    # Check if all elements in original_sequence are present in sequences
    if set(original_sequence) != all_elements:
        return False

    # Generate all possible permutations of elements from sequences
    for permutation in permutations(all_elements):
        permutation_list = list(permutation)
        is_valid_reconstruction = True

        # Check if the current permutation is a valid reconstruction
        current_index = 0
        for sequence in sequences:
            sequence_index = 0
            while sequence_index < len(sequence) and current_index < len(permutation_list):
                if permutation_list[current_index] == sequence[sequence_index]:
                    sequence_index += 1
                current_index += 1

            # Check if the sequence was fully matched
            if sequence_index != len(sequence):
                is_valid_reconstruction = False
                break

        if is_valid_reconstruction:
            if permutation_list == original_sequence:
                # Valid reconstruction found
                return True

    # No valid reconstruction found
    return False

Big(O) Analysis

Time Complexity

O(k!) – The brute force approach involves generating all possible permutations of the 'k' elements present in the smaller sequences to find a match with the original sequence. Generating all permutations for 'k' elements takes k! (k factorial) time. Comparing each permutation with the original sequence of length 'n' takes O(n) time. However, the dominant factor is the generation of permutations, making the overall time complexity O(k!).

Space Complexity

O(N!) – The brute force approach considers all possible orderings of the elements, potentially generating and storing each permutation. Each possible ordering represents a permutation of the original sequence, and there are N! (N factorial) possible permutations of N elements, where N is the length of the original sequence. To store each of these N! permutations for comparison, the algorithm would require space proportional to N!. This leads to an auxiliary space complexity of O(N!).

Optimal Solution

Approach

The problem asks us to determine if a given sequence can be reconstructed from a set of smaller sequences. The key is to use topological sorting and check if there's a unique way to build the original sequence. If there's only one valid order at each step, we can successfully reconstruct the sequence.

Here's how the algorithm would work step-by-step:

First, build a dependency map showing which numbers must come before others based on the smaller sequences.
Also, keep track of how many things each number depends on (its 'in-degree').
Start with numbers that don't depend on anything else (in-degree of zero).
If at any point you have more than one number with an in-degree of zero, it means there's ambiguity, and you can't uniquely reconstruct the sequence.
Pick one number with in-degree zero, add it to your reconstructed sequence, and remove it from the dependency map.
When you remove a number, update the in-degrees of the numbers that depended on it.
Repeat this process until you've either reconstructed the entire sequence or run out of numbers with an in-degree of zero (which means you can't build the original sequence).
Finally, make sure the reconstructed sequence matches the length of the original sequence. If it doesn't, the reconstruction failed.

Code Implementation

def sequence_reconstruction(sequence, sequences):
    number_of_nodes = len(sequence)
    in_degree = {i: 0 for i in range(1, number_of_nodes + 1)}
    adjacency_list = {i: [] for i in range(1, number_of_nodes + 1)}

    for sub_sequence in sequences:
        for i in range(len(sub_sequence) - 1):
            predecessor = sub_sequence[i]
            successor = sub_sequence[i + 1]
            if successor not in adjacency_list[predecessor]:
                adjacency_list[predecessor].append(successor)
                in_degree[successor] += 1

    # Find all nodes with no incoming edges
    queue = [node for node in range(1, number_of_nodes + 1) if in_degree[node] == 0]

    reconstructed_sequence = []

    while queue:
        # If more than one node has in-degree zero, it's ambiguous.
        if len(queue) > 1:
            return False

        current_node = queue.pop(0)
        reconstructed_sequence.append(current_node)

        # Update in-degrees of neighbors.
        for neighbor in adjacency_list[current_node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Ensure that all nodes are visited and the length is right.
    if len(reconstructed_sequence) != number_of_nodes:
        return False

    # Ensures we reconstruct original sequence
    return reconstructed_sequence == sequence

Big(O) Analysis

Time Complexity

O(V + E) – The time complexity is determined by the topological sort process. V represents the number of unique integers (vertices) in the sequences, and E represents the number of dependencies (edges) between them derived from the sequences. Constructing the adjacency list and in-degree map takes O(E) time. The topological sort using a queue visits each vertex and edge once, taking O(V + E) time. Therefore, the overall time complexity is O(V + E).

Space Complexity

O(N) – The algorithm uses a dependency map (adjacency list) and an in-degree array. The dependency map stores, for each number, a list of numbers that depend on it, potentially storing up to N elements (where N is the number of unique elements in the sequences) in total across all lists. The in-degree array stores the in-degree of each number, requiring space proportional to N. Therefore, the auxiliary space complexity is O(N) due to storing the dependency graph and in-degrees.

Edge Cases

Case	How to Handle
Null or empty seqs array	Return false, as an empty sequence of sequences cannot reconstruct any original sequence.
Empty original sequence	Return true if the sequences array is empty or only contains empty sequences; otherwise, return false because non-empty sequences cannot reconstruct an empty sequence.
Sequences contain a number outside the range of [1, n]	Return false, since elements outside the valid range invalidate the reconstruction.
A sequence is longer than n	Return false as the sequences cannot reconstruct a shorter original sequence.
Duplicate numbers within a single sequence	The topological sort should still proceed correctly, but the algorithm needs to be tolerant of multiple dependencies on the same node.
Cycles in the dependency graph implied by the sequences	Return false because the topological sort will not complete, indicating an invalid reconstruction.
No valid reconstruction exists (disconnected components)	Return false, indicating that the given sequences are not sufficient to fully reconstruct the original sequence.
Multiple valid reconstructions exist (ambiguous dependencies)	Return false because the reconstruction must be unique, and multiple valid orderings mean the sequences are insufficient to define a specific ordering.

Null or empty seqs array

How to Handle:

Return false, as an empty sequence of sequences cannot reconstruct any original sequence.

Empty original sequence

How to Handle:

Return true if the sequences array is empty or only contains empty sequences; otherwise, return false because non-empty sequences cannot reconstruct an empty sequence.

Sequences contain a number outside the range of [1, n]

How to Handle:

Return false, since elements outside the valid range invalidate the reconstruction.

A sequence is longer than n

How to Handle:

Return false as the sequences cannot reconstruct a shorter original sequence.

Duplicate numbers within a single sequence

How to Handle:

The topological sort should still proceed correctly, but the algorithm needs to be tolerant of multiple dependencies on the same node.

Cycles in the dependency graph implied by the sequences

How to Handle:

Return false because the topological sort will not complete, indicating an invalid reconstruction.

No valid reconstruction exists (disconnected components)

How to Handle:

Return false, indicating that the given sequences are not sufficient to fully reconstruct the original sequence.

Multiple valid reconstructions exist (ambiguous dependencies)

How to Handle:

Return false because the reconstruction must be unique, and multiple valid orderings mean the sequences are insufficient to define a specific ordering.