Course Schedule
Course Schedule Problem of Graphs – Hard Level Problem
You are given an array prerequisites, where each element prerequisites[i] = [a, b] means you must complete course b before taking course a.
For example, [0, 1] indicates that course 1 must be completed before course 0.
There are a total of numCourses, labeled from 0 to numCourses – 1. Return true if it is possible to complete all courses; otherwise, return false.
Output: true
Explanation: First take course 1 (no prerequisites) and then take course 0.
Output: false
Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.
Constraints :
- 1 <= numCourses <= 1000
- 0 <= prerequisites.length <= 1000
- All prerequisite pairs are unique.
Course Schedule Solution of Graphs
Recommendation for Time and Space Complexity – Aim for a solution with O(V + E) time and space, where V is the number of courses (nodes) and E is the number of prerequisites (edges).
Hints for solving problems
Hint 1
Think of courses as nodes and prerequisites as directed edges in a graph. The goal is to check if the graph has a cycle. If there’s a cycle, it’s impossible to finish all courses. Can you use an algorithm to detect cycles in a graph?
Hint 2
Use DFS to detect cycles. For each course, run a DFS and try to complete its prerequisites by visiting its neighbors. Track the nodes in the current DFS call using a hash set (path). If you revisit a node already in path, a cycle is detected.
Hint 3
Start DFS for each course, using a hash set (path) to track nodes in the current call. If a node is revisited, it indicates a cycle, and we return false. Once DFS for a course finishes with no cycle, clear its neighbors to avoid redundant checks.
There are mainly 2 approach to solve this problem-
- Cycle Detection(DFS) Method
- Topological Sort (Kahn’s Algorithm) Method
1. Cycle Detection(DFS) Method
Treat the courses as a graph and use DFS to detect cycles. Maintain a visited set to track the current path during DFS. If a course is revisited in the same path, a cycle exists, making it impossible to complete all courses.
- Time complexity: O(V + E)
- Space complexity: O(V + E)
where V is the number of courses and E is the number of prerequisites.
Code
class Solution {
// Map each course to its prerequisites
unordered_map<int, vector<int>> preMap;
// Store all courses along the current DFS path
unordered_set<int> visiting;
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
for (int i = 0; i < numCourses; i++) {
preMap[i] = {};
}
for (const auto& prereq : prerequisites) {
preMap[prereq[0]].push_back(prereq[1]);
}
for (int c = 0; c < numCourses; c++) {
if (!dfs(c)) {
return false;
}
}
return true;
}
bool dfs(int crs) {
if (visiting.count(crs)) {
// Cycle detected
return false;
}
if (preMap[crs].empty()) {
return true;
}
visiting.insert(crs);
for (int pre : preMap[crs]) {
if (!dfs(pre)) {
return false;
}
}
visiting.erase(crs);
preMap[crs].clear();
return true;
}
};
public class Solution {
// Map each course to its prerequisites
private Map<Integer, List<Integer>> preMap = new HashMap<>();
// Store all courses along the current DFS path
private Set<Integer> visiting = new HashSet<>();
public boolean canFinish(int numCourses, int[][] prerequisites) {
for (int i = 0; i < numCourses; i++) {
preMap.put(i, new ArrayList<>());
}
for (int[] prereq : prerequisites) {
preMap.get(prereq[0]).add(prereq[1]);
}
for (int c = 0; c < numCourses; c++) {
if (!dfs(c)) {
return false;
}
}
return true;
}
private boolean dfs(int crs) {
if (visiting.contains(crs)) {
// Cycle detected
return false;
}
if (preMap.get(crs).isEmpty()) {
return true;
}
visiting.add(crs);
for (int pre : preMap.get(crs)) {
if (!dfs(pre)) {
return false;
}
}
visiting.remove(crs);
preMap.put(crs, new ArrayList<>());
return true;
}
}
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Map each course to its prerequisites
preMap = {i: [] for i in range(numCourses)}
for crs, pre in prerequisites:
preMap[crs].append(pre)
# Store all courses along the current DFS path
visiting = set()
def dfs(crs):
if crs in visiting:
# Cycle detected
return False
if preMap[crs] == []:
return True
visiting.add(crs)
for pre in preMap[crs]:
if not dfs(pre):
return False
visiting.remove(crs)
preMap[crs] = []
return True
for c in range(numCourses):
if not dfs(c):
return False
return True
class Solution {
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
canFinish(numCourses, prerequisites) {
const preMap = new Map();
for (let i = 0; i < numCourses; i++) { preMap.set(i, []); } for (let [crs, pre] of prerequisites) { preMap.get(crs).push(pre); } // Store all courses along the current DFS path const visiting = new Set(); const dfs = (crs) => {
if (visiting.has(crs)) {
// Cycle detected
return false;
}
if (preMap.get(crs).length === 0) {
return true;
}
visiting.add(crs);
for (let pre of preMap.get(crs)) {
if (!dfs(pre)) {
return false;
}
}
visiting.delete(crs);
preMap.set(crs, []);
return true;
}
for (let c = 0; c < numCourses; c++) {
if (!dfs(c)) {
return false;
}
}
return true;
}
}
2. Topological Sort (Kahn’s Algorithm) Method
Use Kahn’s Algorithm to perform a topological sort. Start with courses that have no prerequisites (in-degree 0) and process them iteratively, reducing the in-degree of their neighbors. If all courses are processed, it’s possible to complete them; otherwise, a cycle exists.
- Time complexity: O(V + E)
- Space complexity: O(V + E)
where V is the number of courses and E is the number of prerequisites.
Code
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> indegree(numCourses, 0);
vector<vector<int>> adj(numCourses);
for (auto& pre : prerequisites) {
indegree[pre[1]]++;
adj[pre[0]].push_back(pre[1]);
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
int finish = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
finish++;
for (int nei : adj[node]) {
indegree[nei]--;
if (indegree[nei] == 0) {
q.push(nei);
}
}
}
return finish == numCourses;
}
};
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
indegree[pre[1]]++;
adj.get(pre[0]).add(pre[1]);
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
int finish = 0;
while (!q.isEmpty()) {
int node = q.poll();
finish++;
for (int nei : adj.get(node)) {
indegree[nei]--;
if (indegree[nei] == 0) {
q.add(nei);
}
}
}
return finish == numCourses;
}
}
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegree = [0] * numCourses
adj = [[] for i in range(numCourses)]
for src, dst in prerequisites:
indegree[dst] += 1
adj[src].append(dst)
q = deque()
for n in range(numCourses):
if indegree[n] == 0:
q.append(n)
finish = 0
while q:
node = q.popleft()
finish += 1
for nei in adj[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
return finish == numCourses
class Solution {
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
canFinish(numCourses, prerequisites) {
let indegree = Array(numCourses).fill(0);
let adj = Array.from({ length: numCourses }, () => []);
for (let [src, dst] of prerequisites) {
indegree[dst]++;
adj[src].push(dst);
}
let q = new Queue();
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
q.push(i);
}
}
let finish = 0;
while (!q.isEmpty()) {
let node = q.pop();
finish++;
for (let nei of adj[node]) {
indegree[nei]--;
if (indegree[nei] === 0) {
q.push(nei);
}
}
}
return finish === numCourses;
}
}
