You are given a total of numCourses courses labeled from 0 to numCourses - 1, and an array of prerequisite pairs where prerequisites[i] = [a, b] means you must take course b before course a. Return true if it is possible to finish all courses, or false if there is a circular dependency that makes it impossible.
Example
numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true
Course 0 has no prerequisites, course 1 requires 0, course 2 requires 1, and course 3 requires 2. Taking them in order 0 -> 1 -> 2 -> 3 satisfies all prerequisites with no circular dependencies.
Model courses as a directed graph and detect if there's a cycle. Build an adjacency list and compute each node's in-degree. Use BFS (Kahn's algorithm) starting from all nodes with 0 in-degree. If you can process all nodes, there's no cycle and all courses can be finished.
Why this works
Course prerequisites form a directed graph. If there is a cycle (A requires B, B requires C, C requires A), those courses can never be completed. Kahn’s algorithm detects cycles by peeling off nodes with no incoming edges layer by layer. If every node gets peeled off, there is no cycle and all courses are completable.
Step by step
- Build the graph — for each prerequisite pair
[course, prereq], add an edge from prereq to course. Track each node’s in-degree (number of prerequisites). - Seed the queue — enqueue all courses with in-degree 0 (no prerequisites needed).
- Process layer by layer — dequeue a course, increment the “taken” count, and reduce the in-degree of all courses that depend on it.
- Enqueue newly free courses — when a course’s in-degree drops to 0, all its prerequisites are satisfied, so enqueue it.
- Check completeness — if the count of taken courses equals the total, return true. Otherwise a cycle prevented some courses from being processed.
Time: O(V+E)
Space: O(V+E)
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[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]); // prereq → course edge
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i); // start with courses that have no prereqs
}
}
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++; // this course can be taken
for (int neighbor : graph.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor); // all prereqs met, ready to take
}
}
}
return count == numCourses; // if not all processed, there's a cycle
}
}
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]); // prereq → course edge
inDegree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i); // start with courses that have no prereqs
}
}
int count = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
count++; // this course can be taken
for (int neighbor : graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.push(neighbor); // all prereqs met, ready to take
}
}
}
return count == numCourses; // if not all processed, there's a cycle
}
};
from collections import deque
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course) # prereq → course edge
in_degree[course] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0) # start with courses that have no prereqs
count = 0
while queue:
node = queue.popleft()
count += 1 # this course can be taken
for neighbor in graph[node]:
in_degree[neighbor] -= 1 # one prereq satisfied
if in_degree[neighbor] == 0:
queue.append(neighbor) # all prereqs met, ready to take
return count == numCourses # if not all processed, there's a cycle