Leetcode 210. Course Schedule II

Problem Explanation

Problem

The problem is a graph theory problem which presents a case where one has list of university courses with their prerequisites to be completed. The goal is to find a possible order that the courses could be undertaken, respecting their prerequisites. For example, if course 1 is prerequisite for course 0, then course 1 must be taken before course 0. As per the problem statement, there can be multiple correct orders and we are required to return any one of them. In case it is impossible to complete all courses, an empty array should be returned.

This is an application of topological sorting, an algorithm applied on Directed Acyclic Graphs (DAG) for linear ordering of vertices such that for every edge (u->v), u comes before v in that ordering.

Example

Walkthrough of an example (4, [[1,0],[2,0],[3,1],[3,2]]):

Here we have 4 courses numbered from 0 to 3, with some courses requiring prerequisites.

• Course 1 and 2 require the completion of course 0.
• Course 3 requires the completion of courses 1 and 2.

After visualizing the requirements, one of the possible course ordering is [0,1,2,3] or [0,2,1,3]. We can choose any ordering as it fits the prerequisite requirements.

Solution Approach

The solution uses Depth First Search (DFS) and topological sorting to find a valid ordering. We first check if there are any cycles in the graph formed by the prerequisites. This is because a cycle means that we have a circular dependency, making it impossible to finish all courses.

The algorithm is as follows:

1. For each vertex in the graph (in our case, each course), we start a depth-first search.
2. To detect a cycle, we mark our current vertex as kVisiting.
3. If we reach a vertex that is still in the kVisiting state, this means we have a cycle and return true to indicate that it's impossible to take all courses.
4. If the vertex is already in the kVisited state, we skip it.
5. After we finish visiting all neighbours, we mark the current vertex as kVisited and add it to our result list.
6. The search goes on until we have visited all vertices.

If we don't detect any cycles, we have a topological sorting of the courses in the ans list. However, because of the depth-first search, our list is in reverse order, so we need to reverse it before returning.

ASCII Illustration

The graph representation of the input list:

1
2
3        0
4    ↗      ↖
5 1       ↖
6     ↖       
7    3 ↗  
8      ↘
9            ↗
10         2 ↗

Python Solution

1
2python
3class Solution:
4    def findOrder(self, numCourses, prerequisites):
5        res, graph, visit = [], {i: [] for i in xrange(numCourses)}, [0 for i in xrange(numCourses)]
6        for pair in prerequisites:
7            graph[pair[0]].append(pair[1])
8        def dfs(i):
9            if visit[i] == -1:
10                return False
11            if visit[i] == 1:
12                return True
13            visit[i] = -1
14            for j in graph[i]:
15                if not dfs(j):
16                    return False
17            visit[i] = 1
18            res.append(i)
19            return True
20        for i in xrange(numCourses):
21            if not dfs(i):
22                return []
23        return res

Java Solution

1
2java
3public int[] findOrder(int numCourses, int[][] prerequisites) {
4    Map<Integer, List<Integer>> courseMap = new HashMap<>();
5    for(int i=0; i<prerequisites.length; i++) {
6        if(courseMap.containsKey(prerequisites[i][0])) {
7            courseMap.get(prerequisites[i][0]).add(prerequisites[i][1]);
8        } else {
9            List<Integer> preList = new ArrayList<>();
10            preList.add(prerequisites[i][1]);
11            courseMap.put(prerequisites[i][0], preList);
12        }
13    }
14
15    boolean[] visited = new boolean[numCourses];
16    boolean[] checked = new boolean[numCourses];
17    Deque<Integer> stack = new ArrayDeque<>();
18
19    for(int currCourse=0; currCourse<numCourses; currCourse++) {
20        if(!checked[currCourse] && !canFinishDFS(courseMap, visited, checked, stack, currCourse)) {
21            return new int[0];
22        }
23    }
24
25    int i = 0; 
26    int[] courseOrder = new int[numCourses];
27    for(int courseId: stack) {
28        courseOrder[i++] = courseId;
29    }
30    return courseOrder;
31}
32
33public boolean canFinishDFS(Map<Integer, List<Integer>> courseMap, boolean[] visited, boolean[] checked, Deque<Integer> stack, int currCourse) {
34    if(visited[currCourse]) return false;
35    if(checked[currCourse]) return true;
36
37    if(courseMap.containsKey(currCourse)) {
38        visited[currCourse] = true;
39        for(int pre: courseMap.get(currCourse)) {
40            if(!canFinishDFS(courseMap, visited, checked, stack, pre)) {
41                return false;
42            }
43        }
44        visited[currCourse] = false;
45    }
46
47    checked[currCourse] = true;
48    stack.push(currCourse);
49
50    return true;
51}

JavaScript Solution

1
2javascript
3var findOrder = function(numCourses, prerequisites) {
4    let result = [];
5    let adjList = new Map();
6    let seen = new Set();
7    let visiting = new Set();
8
9    // create graph
10    for (let i = 0; i < numCourses; i++) adjList.set(i, []);
11    for (let [v, e] of prerequisites) adjList.get(v).push(e);
12
13    // DFS: return true if cycle is detected, basically if a node is pointing back to itself
14    let hasCycle = function (node) {
15        visiting.add(node);
16        for (let neighbor of adjList.get(node)) {
17            if (!seen.has(neighbor)) {
18                if (visiting.has(neighbor)) return true;
19                if (hasCycle(neighbor)) return true;  
20            }
21        }
22        visiting.delete(node);
23        seen.add(node);
24        result.push(node);
25        return false;
26    }
27
28    for (let [node] of adjList) {
29        if (!seen.has(node)) {
30            if (hasCycle(node)) return [];
31        }
32    }
33    return result;
34};

C++ Solution

1
2C++
3class Solution {
4public:
5    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
6        graph_ = vector<vector<int>>(numCourses);
7        for (const auto& p : prerequisites) {
8            graph_[p[1]].push_back(p[0]);
9        }
10        // states: 0 = unkonwn, 1 == visiting, 2 = visited
11        vector<int> v(numCourses, 0);
12        for (int i = 0; i < numCourses; ++i) {
13            if (v[i] == 0 && !DFS(i, v)) {
14                return false;
15            }
16        }
17        return true;
18    }
19private:
20    vector<vector<int>> graph_;
21    bool DFS(int cur, vector<int>& v) {
22        v[cur] = 1;
23        for (const auto t : graph_[cur]) {
24            if (v[t] == 0) {     // Unknown, we recursively visit it.
25                if (!DFS(t, v)) return false;
26            } else if(v[t] == 1){ // In visiting, then we find a cycle.
27                return false;
28            }
29        }
30        v[cur] = 2; // marked as visited
31        return true;
32    }
33};

C# Solution

1
2C#
3public class Solution {
4    private const int WHITE = 1;
5    private const int GRAY = 2;
6    private const int BLACK = 3;
7
8    bool isPossible;
9    Dictionary<int, int> color;
10    Dictionary<int, List<int>> adjList;
11    List<int> topologicalOrder;
12
13    private void Init(int numCourses) {
14        this.isPossible = true;
15        this.color = new Dictionary<int, int>();
16        this.adjList = new Dictionary<int, List<int>>();
17        this.topologicalOrder = new List<int>();
18
19        // By default all vertices are WHITE
20        for (int i = 0; i < numCourses; i++) {
21            this.color.Add(i, WHITE);
22        }    
23    }
24
25    private void DFS(int node) {
26
27        // Don't recurse further if we found a cycle already
28        if (!this.isPossible) {
29            return;
30        }
31
32        // Start the recursion
33        this.color[node] = GRAY;
34
35        // Traverse on neighboring vertices
36        foreach (var neighbor in this.adjList.GetValueOrDefault(node)) {
37            if (this.color.GetValueOrDefault(neighbor, WHITE) == WHITE) {
38                this.DFS(neighbor);
39            } else if (this.color[neighbor] == GRAY) {
40                // An edge to a GRAY vertex represents a cycle
41                this.isPossible = false;
42            }
43        }
44
45        // Recursion ends. We mark it as black
46        this.color[node] = BLACK;
47        this.topologicalOrder.Add(node);
48    }
49
50    public int[] FindOrder(int numCourses, int[][] prerequisites) {
51        this.Init(numCourses);
52
53        // Create the adjacency list representation of the graph
54        for (int i = 0; i < prerequisites.Length; i++) {
55            int dest = prerequisites[i][0];
56            int src = prerequisites[i][1];
57            List<int> lst = adjList.ContainsKey(src) ? adjList[src] : new List<int>();
58            lst.Add(dest);
59            adjList[src] = lst;
60        }
61
62        // If the node is unprocessed, then call DFS on it.
63        for (int i = 0; i < numCourses; i++) {
64            if (this.color[i] == WHITE) {
65                this.DFS(i);
66            }
67        }
68
69        int[] order;
70        if (this.isPossible) {
71            order = new int[numCourses];
72            for (int i = 0; i < numCourses; i++) {
73                order[i] = this.topologicalOrder[numCourses - i - 1];
74            }
75        } else {
76            order = new int[0];
77        }
78
79        return order;
80    }
81}

The preceding solutions in Python, Java, JavaScript, C++ and C# effectively tackles the course scheduling problem using topological sorting and DFS. However, like most problems in computer science, there could be other ways to implement the solutions using different data structures and various sorting algorithms.

Variations

1. Breadth-first Search (BFS) and Degree of Vertex: BFS can be an alternative approach to DFS and topological sorting. In this alternative approach, we can consider the 'degree' of the vertex, which refers to the number of prerequisites for a course. We can leverage a queue data structure to keep track of all nodes with 0 degree, remove them from the graph and reduce the degree of all nodes that are connected to the background nodes. Do this iteratively until there are no nodes of degree 0 but there are still nodes left in the graph, the graph has a cycle meaning it's impossible to finish all courses.

2. Detecting cycles using Union-Find: Union-Find or Disjoint Set Union (DSU) data structure can be used to detect cycles in a graph and hence can be applied in this problem similarly to DFS.

3. Priority-first Search (PFS): Another alternative to DFS and BFS can be Priority-first Search. In PFS, nodes are often chosen based on a priority function f(n). This priority can be based on the number of prerequisites and other parameters.

Note that each variation has potential to provide an optimal solution but the efficiency of each can vary depending on the specific inputs.

These solutions for course scheduling are a good example of how graph theory can be applied in real-world applications, demonstrating the utility of key algorithms in navigating connectivity-based problems. Equally important is the fact that these solutions emphasize the importance of careful thought in data structure selection and thorough testing in different implementation scenarios for optimized outcomes.