444. Sequence Reconstruction

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

// Two arrays
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    if (seqs.empty()) return false;
    int n = org.size(), cnt = n - 1; // cnt: edges need to be verified
    // flags: mark if the current number and previous number are in correct position
    vector<bool> flags(n + 1, false);
    vector<int> pos(n + 1, 0); 
    bool existed = false; // handle corner case if seqs only has empty sequence
    for (int i = 0; i < n; ++i) pos[org[i]] = i;
    for (const auto& seq : seqs) {
        for (int i = 0; i < seq.size(); ++i) {
            if (!existed) existed = true;
            if (seq[i] <= 0 || seq[i] > n) return false;
            if (i == 0) continue;
            int pre = seq[i - 1], cur = seq[i];
            if (pos[pre] >= pos[cur]) return false;
            if (!flags[cur] && pos[pre] + 1 == pos[cur]) {
                flags[cur] = true;
                --cnt;
            }
        }
    }
    return cnt == 0 && existed;
}

// Two hashmaps
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    // pre: the relation between positions of current number and previous number in the org array
    unordered_map<int, int> pos, pre;
    for (int i = 0; i < org.size(); ++i) pos[org[i]] = i;
    for (auto& seq : seqs) {
        for (int i = 0; i < seq.size(); ++i) {
            if (!pos.count(seq[i])) return false;
            if (i > 0 && pos[seq[i - 1]] >= pos[seq[i]]) return false;
            if (!pre.count(seq[i])) {
                pre[seq[i]] = (i > 0) ? pos[seq[i - 1]] : -1;
            } else {
                pre[seq[i]] = max(pre[seq[i]], ((i > 0) ? pos[seq[i - 1]] : -1));
            }
        }
    }
    for (int i = 0; i < org.size(); ++i) {
        if (pre[org[i]] != i - 1) return false;
    }
    return true;
}

// BFS Topological Sort
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    int n = org.size();
    vector<unordered_set<int> > graph(n + 1); // Adjacency list
    vector<int> indegree(n + 1);
    bool empty = true; // handle corner case if seqs only has empty sequence
    for (const vector<int>& seq : seqs) {
        if (seq.empty()) continue;
        if (empty) empty = false;
        for (int i = 0; i < seq.size(); ++i) {
            if (seq[i] <= 0 || seq[i] > n) return false; // check input validity
            if (i == 0) continue;
            if (!graph[seq[i - 1]].count(seq[i])) {
                graph[seq[i - 1]].insert(seq[i]);
                ++indegree[seq[i]];
            }
        }
    }
    if (empty) return false;
    queue<int> q;
    // i == 0 is not used in indegree array
    for (int i = 1; i <= n; ++i) {
        if (indegree[i] == 0) q.push(i);
    }
    int idx = 0;
    while (!q.empty()) {
        if (q.size() > 1) return false; // the size of queue should always be 1
        int cur = q.front(); q.pop();
        // The order should be the same as org
        if (cur != org[idx++]) return false;
        for (int i : graph[cur]) {
            if (--indegree[i] == 0) q.push(i);
        }
    }
    return idx == n;
}