TLE graph topological sort solution, extension discussion and open for comments


  • 0

    Natually, I was trying to create a directed graph and do a topological sort to reconstruct the original sequence while comparing with the given org sequence whenever a unique zero-indegree node can be found. However, I got TLE because later I saw the optimized solution should have O(N+sum_i L_i) time, where L_i is the length of given seqs[i].
    Then I checked my graph solution, which costs O(N+sum_i L_i) time alone to create the graph and uses another O(N^2) time to do topological sort. So I guess this is why I got TLE (?).
    Finally, I am wondering how the optimized solution could achieve just in linear time. It is probably because that the original sequence is also given as a reference. If only vector<vector<int>> seqs is given to ask to restore a shortest possible (no duplicate) original sequence, I guess the problem will be much more difficult and probably cost more time, isn't it? Any comment is appreciated!

        unordered_map<int, unordered_set<int>> out; // out neighbors
        unordered_map<int, int> indeg; // in degree (count of in-neighbors)
        
        void getGraph(vector<int>& org, vector<vector<int>>& seqs) {
            for (int x:org) indeg[x] = 0;
            for (auto& seq : seqs) {
                int n = seq.size();
                for (int i = 1; i < n; ++i) {
                    auto res = out[seq[i-1]].insert(seq[i]); if (res.second) indeg[seq[i]]++;
                }
            }
        }
        
        bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
            if (org.empty() != seqs.empty()) return false;
            getGraph(org, seqs);
            int counter = 0;
            while (!indeg.empty()) {
              bool found = false;
              for (auto& x:indeg) {
                  if (x.second) continue;
                  if (!found && x.first == org[counter]) { found = true; }
                  else return false;
              }
              if (found) {
                  for (auto& nb:out[org[counter]]) indeg[nb]--;
                  out.erase(org[counter]);
                  indeg.erase(org[counter]);
                  counter++;
              }
              else return false;
            }
            
            return true;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.