Formatted question description: https://leetcode.ca/all/444.html

444. Sequence Reconstruction

Level

Medium

Description

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example 1:

Input:

org: [1,2,3], seqs: [[1,2],[1,3]]

Output:

false

Explanation:

[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input:

org: [1,2,3], seqs: [[1,2]]

Output:

false

Explanation:

The reconstructed sequence can only be [1,2].

Example 3:

Input:

org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:

true

Explanation:

The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input:

org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:

true

Solution

If only one sequence can be reconstructed from seqs, then seqs must contain all adjacent subsequences of length 2 in org. It is possible that seqs contains a subsequence that has length greater than 2 and the elements in the subsequence are all adjacent in org. Besides, seqs must contain all the numbers in org but can’t contain any number that is not in org.

Use a map to store each number and its corresponding index in org. Use an array of type boolean to store whether each adjacent subsequence is contained in seqs. Use a set to store the numbers in seqs.

Loop over org to fill in the map. For each sequence in seqs, first check all the numbers in the sequence. If a number is greater than org.length, then the number can’t be in org, so return false. Otherwise, add the number to the set. Then check each pair of adjacent numbers. If two adjacet numbers’ indices in org are adjacent and the former number’s index is less than the latter number’s index, then set the element at the former number’s index in the boolean array to true. If the former number’s index is greater than or equal to the latter number’s index, then there is a conflict, so return false.

After the loop, check the set’s size. If the set’s size is less than org.length, then return false. Then check all the elements in the boolean array. If there is a false, then return false. Otherwise, return true.

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        if (seqs == null)
            return org == null;
        if (seqs.size() == 0)
            return org.length == 0;
        Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
        int length = org.length;
        for (int i = 0; i < length; i++)
            numIndexMap.put(org[i], i);
        boolean[] adjacentSequences = new boolean[length - 1];
        Set<Integer> set = new HashSet<Integer>();
        for (List<Integer> sequence : seqs) {
            for (int num : sequence) {
                if (num > length)
                    return false;
                else
                    set.add(num);
            }
            int size = sequence.size();
            for (int i = 1; i < size; i++) {
                int num1 = sequence.get(i - 1), num2 = sequence.get(i);
                int index1 = numIndexMap.getOrDefault(num1, -1);
                int index2 = numIndexMap.getOrDefault(num2, -1);
                if (index1 < 0 || index2 < 0 || index1 >= index2)
                    return false;
                if (index2 - index1 == 1)
                    adjacentSequences[index1] = true;
            }
        }
        if (set.size() < length)
            return false;
        for (boolean adjacentSequence : adjacentSequences) {
            if (!adjacentSequence)
                return false;
        }
        return true;
    }
}

All Problems

All Solutions