Sequence Reconstruction

• Lintcode : 605 / Leetcode : 444
• Level : Medium

Problem

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
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

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    bool sequenceReconstruction(vector<int> &org, vector<vector<int>> &seqs) {
        unordered_map<int, unordered_multiset<int>> edges;
        unordered_map<int, int> degree;
        for (auto seq : seqs) {
            for (int i = 0; i < seq.size(); i++) {
                degree[seq[i]];
                if (i + 1 < seq.size()) {
                    edges[seq[i]].insert(seq[i + 1]);
                    degree[seq[i + 1]]++;
                }
            }
        }

        queue<int> q;
        vector<int> ans;
        for (auto it = degree.begin(); it != degree.end(); it++) {
            if (it -> second == 0) q.push(it -> first);  
        }
        while (!q.empty()) {
            if (q.size() > 1) return false;
            int h = q.front(); q.pop();
            ans.push_back(h);
            for (auto it = edges[h].begin(); it != edges[h].end(); it++) {
                degree[*it]--;
                if (degree[*it] == 0) q.push(*it);
            }
        }
        if (org.size() != ans.size()) return false;
        for (int i = 0; i < org.size(); i++) {
            if (org[i] != ans[i]) return false;
        }
        return true;
    }
};

tags: topological sorting

​

Topological Sorting

• Lintcode : 127 / Leetcode :
• Level : Medium

Problem

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.

Example
For graph as follow:

图片

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
Challenge
Can you do it in both BFS and DFS?

Clarification
Learn more about representation of graphs

Notice
You can assume that there is at least one topological order in the graph.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(v edges)
space: O(v edges)

Answer

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
        unordered_map<DirectedGraphNode*, set<DirectedGraphNode*>> edges;
        unordered_map<DirectedGraphNode*, int> degree;
        for (auto g : graph) {
            degree[g];
            for (int i = 0; i < g -> neighbors.size(); i++) {
                edges[g].insert(g -> neighbors[i]);
                degree[g -> neighbors[i]]++;
            }
        }
        queue<DirectedGraphNode*> q;
        vector<DirectedGraphNode*> ans;
        for (auto it = degree.begin(); it != degree.end(); it++) {
            if (it -> second == 0) q.push(it -> first);
        }

        while (!q.empty()) {
            DirectedGraphNode* n = q.front(); q.pop();
            ans.push_back(n);
            for (auto it = edges[n].begin(); it != edges[n].end(); it++) {
                degree[*it]--;
                if (degree[*it] == 0) q.push(*it);
            }
        }
        return ans;
    }
};

tags: topological sorting

​

Course Schedule II

• Lintcode : 616 / Leetcode : 210
• Level : Medium

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example
Example 1:

Input: n = 2, prerequisites = [[1,0]] 
Output: [0,1]
Example 2:

Input: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 
Output: [0,1,2,3] or [0,2,1,3]

Concept & Algorithm

筆記
筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>> &prerequisites) {
        vector<unordered_multiset<int>> edge(numCourses);
        vector<int> degrees(numCourses, 0);
        for (int i = 0; i < prerequisites.size(); i++) {
            edge[prerequisites[i].second].insert(prerequisites[i].first);
            degrees[prerequisites[i].first]++;
        }
        queue<int> q;
        vector<int> ans;
        for(int i = 0; i < numCourses; i++) {
            if (degrees[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int h = q.front(); q.pop();
            ans.push_back(h);
            for (auto it = edge[h].begin(); it != edge[h].end(); it++) {
                degrees[*it]--;
                if (degrees[*it] == 0) q.push(*it);
            }
        }
        return ans.size() == numCourses ? ans : vector<int>();
    }
};

tags: topological sorting

​

Course Schedule

• Lintcode : 615 / Leetcode : 207
• Level : Medium

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example
Example 1:

Input: n = 2, prerequisites = [[1,0]] 
Output: true
Example 2:

Input: n = 2, prerequisites = [[1,0],[0,1]] 
Output: false

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        // [[5,8],[3,5],[1,9],[4,5],[0,2],[1,9],[7,8],[4,9]]
        // used set<int> will cause error
        vector<unordered_multiset<int>> edges(numCourses);
        vector<int> degree(numCourses, 0);
        for (auto p : prerequisites) {
            edges[p.second].insert(p.first);
            degree[p.first]++;
        }
        queue<int> q;
        set<int> course;
        for (int i = 0; i < degree.size(); i++) {
            if (degree[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int head = q.front(); q.pop();
            course.insert(head);
            for (auto it = edges[head].begin(); it != edges[head].end(); it++) {
                degree[*it]--;
                if (degree[*it] == 0) {
                    q.push(*it);
                }
            }
        }
        return course.size() == numCourses;
    }
};

tags: topological sorting

​