444. Sequence Reconstruction (Medium)

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 ≤ 10^4$$. 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: Hash Table

For org to be uniquely reconstructible from seqs we need to satisfy 2 conditions:

1. Every sequence in seqs should be a subsequence in org. This part is obvious.
2. Every 2 consecutive elements in org should be consecutive elements in some sequence from seqs. Why is that? Well, suppose condition 1 is satisfied. Then for 2 any consecutive elements x and y in org we have 2 options.
   • We have both x and y in some sequence from seqs. Then (as condition 1 is satisfied) they must be consequtive elements in this sequence.
   • There is no sequence in seqs that contains both x and y. In this case we cannot uniquely reconstruct org from seqs as sequence with x and y switched would also be a valid original sequence for seqs.

So this are 2 necessary criterions. It is pretty easy to see that this are also sufficient criterions for org to be uniquely reconstructible (there is only 1 way to reconstruct sequence when we know that condition 2 is satisfied).

To implement this idea I have idxs hash that maps item to its index in org sequence to check condition 1. And I have pairs set that holds all consequitive element pairs for sequences from seqs to check condition 2 (I also consider first elements to be paired with previous undefined elements, it is necessary to check this).

version 1: 252ms

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n = org.size();
        vector<int> pos(n+1,0);
        unordered_set<int> num;
        unordered_set<string> s;
        for (int i = 0; i < n; ++i) pos[org[i]] = i;
        for (auto& seq: seqs) {
            for (int i = 0; i < seq.size(); ++i) {
                if (seq[i] <= 0 || seq[i] > n) return false;
                num.insert(seq[i]);
                if (i == 0) continue;
                if (pos[seq[i-1]] >= pos[seq[i]]) return false;
                s.insert(to_string(seq[i-1])+" "+to_string(seq[i]));
            }
        }
        if (num.size() != n) return false;
        for (int i = 1; i < n; ++i) {
            if (s.count(to_string(org[i-1])+" "+to_string(org[i])) == 0) return false;
        }
        return true;
    }
};

version 2: 112ms

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n = org.size(), toMatch = n-1;
        vector<int> pos(n+1,0), flags(n+1,0);
        unordered_set<int> num;
        for (int i = 0; i < n; ++i) pos[org[i]] = i;
        for (auto& seq: seqs) {
            for (int i = 0; i < seq.size(); ++i) {
                if (seq[i] <= 0 || seq[i] > n) return false;
                num.insert(seq[i]);
                if (i == 0) continue;
                int x = seq[i-1], y = seq[i];
                if (pos[x] >= pos[y]) return false;
                if (flags[x] == 0 && pos[x]+1 == pos[y]) {
                    flags[x] = 1, --toMatch;
                }
            }
        }
        return num.size() == n && toMatch == 0;
    }
};