Course Schedule
Medium Cycle detection with Kahn's algorithm
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Courses have prerequisite pairs [a, b] meaning b must come before a. Decide whether all courses can be finished.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you finish all courses given their prerequisites (is there no cycle)?
Why this works: Kahn's algorithm keeps taking courses with no remaining prerequisites. If some courses are never taken, they sit on a cycle.
Example: 2 courses, [1 needs 0], [0 needs 1]
no course starts with 0 prerequisites → 0 taken → false✦Hints open one at a time
↗Approach
Build edges b → a and in-degrees. Queue all courses with in-degree 0; when a course is taken, reduce its neighbours' in-degrees. If all n courses get taken, there's no cycle.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]); // b before a
indeg[p[0]]++;
}
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
int taken = 0;
while (!q.isEmpty()) {
int u = q.poll();
taken++;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return taken == numCourses; // leftover courses sit on a cycle
}
}!Common mistake
Reversing the edge direction — it still detects cycles here, but gives the wrong order in Course Schedule II.
- Time: O(V + E).
- Space: O(V + E).