Leetcode 444 Solution

This article provides solution to leetcode question 444 (sequence-reconstruction)

https://leetcode.com/problems/sequence-reconstruction

Solution

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n = org.size();
        vector<int> pos(n + 1);
        vector<bool> flags(n + 1);
        int flags_cnt = n - 1;

        for (int i = 0; i < org.size(); i++)
            pos[org[i]] = i;

        bool checked = false;
        for (auto seq : seqs)
        {
            for (int i = 0; i < seq.size(); i++)
            {
                checked = true;
                if (0 >= seq[i] || seq[i] > n)
                    return false;

                if (i == 0)
                    continue;

                int from = seq[i - 1];
                int to = seq[i];

                if (pos[from] >= pos[to])
                    return false;

                if (pos[from] + 1 == pos[to] && flags[from] == 0)
                {
                    flags[from] = 1;
                    flags_cnt--;
                }
            }
        }

        return flags_cnt == 0 && checked;
    }
};