Course Schedule
You have numCourses courses labeled 0 to numCourses - 1, and an array prerequisites where prerequisites[i] = [a, b] means you must finish course b before you can take course a. Return true if there is some order in which you can finish every course, and false otherwise. Some courses have no prerequisites, and requirements can chain: if 2 needs 1 and 1 needs 0, then 0 must come before both.
Examples
numCourses = 2, prerequisites = [[1,0]] returns true
Course 1 needs course 0, so you take 0 first and then 1.
numCourses = 2, prerequisites = [[1,0],[0,1]] returns false
Course 1 needs 0 and course 0 needs 1. Each one waits on the other, so neither can ever be started.
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
Hints
When is a set of prerequisite dependencies actually finishable?
Model as a directed graph and detect cycles via Kahn's BFS using in-degrees.
Build adjacency lists and an indegree array from the prerequisites. Push every course with indegree 0 into a queue. Pop, increment a finished counter, and decrement indegrees of its neighbors, enqueuing any that hit zero. Return finished == numCourses.
Drill This: Your Approach First
Approach
Treat each pair [a, b] as a directed edge b -> a and count each course's in-degree, the number of prerequisites it still waits on. Queue every course with in-degree 0. Repeatedly take one, count it as finished, and decrement the in-degree of each course that depends on it, queuing any that reach 0 (Kahn's algorithm). A course on a cycle never reaches 0, so every course finishes exactly when there's no cycle. O(V + E) time and space, V = numCourses, E = number of pairs.
Time
O(V + E)
Space
O(V + E)
Pitfall
Solutions
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] e : prerequisites) {
graph.get(e[1]).add(e[0]);
indeg[e[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) queue.offer(i);
int taken = 0;
while (!queue.isEmpty()) {
int c = queue.poll();
taken++;
for (int nb : graph.get(c)) {
if (--indeg[nb] == 0) queue.offer(nb);
}
}
return taken == numCourses;
}
}from collections import deque, defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites) -> bool:
graph = defaultdict(list)
indeg = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
queue = deque(i for i in range(numCourses) if indeg[i] == 0)
taken = 0
while queue:
c = queue.popleft()
taken += 1
for nb in graph[c]:
indeg[nb] -= 1
if indeg[nb] == 0:
queue.append(nb)
return taken == numCourses