There are numCourses courses labeled 0 to numCourses - 1.
You are given an array prerequisites where prerequisites[i] = [a, b]
means you must take course b before course a.
Return true if you can finish all courses, otherwise return false.
Essentially: can all courses be completed? This is equivalent to asking whether
the prerequisite dependency graph has no cycles.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Course 0 → Course 1. No cycle. Possible.
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 0 requires 1 and 1 requires 0 — cycle, impossible.
Constraints:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
Contents
- Solution 1 — Kahn's Algorithm (BFS / Indegree)
- Solution 2 — DFS with 3-Color Marking
- Complexity Analysis
Kahn's Algorithm (BFS)
Build the graph from prerequisites. Run topological sort.
If we can process all numCourses nodes, no cycle exists → return true.
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] pre : prerequisites) {
int course = pre[0], prereq = pre[1];
adj.get(prereq).add(course); // prereq → course
indegree[course]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) queue.offer(i); // no prerequisites
}
int processed = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
processed++;
for (int next : adj.get(course)) {
indegree[next]--;
if (indegree[next] == 0) queue.offer(next);
}
}
return processed == numCourses; // true if all courses were processable
}
DFS with 3-Color Marking
Use three states for each node:
- 0 — unvisited
- 1 — currently being processed (in the current DFS path)
- 2 — fully processed (safe, no cycle through this node)
If during DFS we encounter a node with state 1, we've found a cycle.
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
}
int[] state = new int[numCourses]; // 0=unvisited, 1=visiting, 2=done
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0 && hasCycle(i, adj, state)) return false;
}
return true;
}
private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
state[node] = 1; // mark as visiting
for (int neighbor : adj.get(node)) {
if (state[neighbor] == 1) return true; // back edge → cycle
if (state[neighbor] == 0 && hasCycle(neighbor, adj, state)) return true;
}
state[node] = 2; // mark as fully processed
return false;
}
- Time: O(V + E) — V = numCourses, E = prerequisites.length.
- Space: O(V + E) — adjacency list + indegree/state array.