Back to DSA
Course Schedule
mediumThere are n courses labeled 0 through n-1 with prerequisite constraints: some courses must be completed before others. Given these dependency pairs, determine whether it is possible to complete all courses (i.e., the dependency graph contains no cycles).
Examples
Example 1:
Input:
numCourses = 3, prerequisites = [[1,0],[2,1]]Output:
trueExplanation: Take course 0, then 1, then 2. The dependency chain has no cycle.
Example 2:
Input:
numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]Output:
falseExplanation: Courses 0, 1, and 2 form a circular dependency.
Hints
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
for (int next : graph.get(node)) {
if (--inDegree[next] == 0) queue.offer(next);
}
}
return count == numCourses;
}
}Time complexity
O(V + E)Space complexity
O(V + E)