TL;DR
Build the prerequisite graph and detect a cycle — Kahn’s BFS topological sort or DFS three-coloring, both O(V + E) time and space.
Approach 1 — Brute force (repeatedly strip courses you can take)
Scan the list, take any course whose prerequisites are all already taken, mark it done, and repeat the whole scan until nothing changes. If everything gets taken, return True.
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
taken = [False] * numCourses
remaining = numCourses
while True:
progressed = False
for course in range(numCourses):
if taken[course]:
continue
if all(taken[b] for a, b in prerequisites if a == course):
taken[course] = True
remaining -= 1
progressed = True
if not progressed:
return remaining == 0
Complexity: each outer pass rescans every prerequisite, and you may need up to numCourses passes → O(V · E). This is Kahn’s algorithm done inefficiently; the next approach does the same peeling in linear time.
Approach 2 — Kahn’s algorithm (BFS topological sort)
A course with in-degree 0 has no unmet prerequisites, so it can be taken now. Taking it removes it as a prerequisite for its dependents, lowering their in-degrees. Keep a queue of the currently-takeable courses. If all numCourses get taken, the graph is acyclic; if the queue empties early, the remaining courses form a cycle. This in-degree peeling is Kahn’s algorithm.
from collections import deque
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites: # b must come before a: edge b -> a
adj[b].append(a)
indegree[a] += 1
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in adj[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return taken == numCourses
Walkthrough (numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]). The prerequisites form this graph:
flowchart LR
0 --> 1
0 --> 2
1 --> 3
2 --> 3
- Edges:
0→1, 0→2, 1→3, 2→3. In-degrees: 0:0, 1:1, 2:1, 3:2. Queue [0].
- Take 0 (
taken=1); decrement 1→0 and 2→0, enqueue both. Queue [1,2].
- Take 1 (
taken=2); 3 drops to 1. Take 2 (taken=3); 3 drops to 0, enqueue. Take 3 (taken=4).
taken == 4 == numCourses → True.
On the cyclic [[1,0],[0,1]], both courses start at in-degree 1, the queue is empty from the start, taken stays 0 → False.
Complexity: building the graph is O(E); each node and edge is processed once → O(V + E) time, O(V + E) space.
Approach 3 — DFS three-color cycle detection
Run DFS and track each node’s state: WHITE (unseen), GRAY (on the current recursion stack), BLACK (fully explored). Reaching a GRAY node means a back edge, which is a cycle. Nodes marked BLACK are known-safe and never re-explored, keeping the traversal linear. Use DFS when you also want the recursion structure (e.g. to identify which cycle); use Kahn’s to avoid recursion limits and get a valid order as a byproduct.
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
for a, b in prerequisites:
adj[b].append(a)
WHITE, GRAY, BLACK = 0, 1, 2
state = [WHITE] * numCourses
def has_cycle(course: int) -> bool:
state[course] = GRAY
for nxt in adj[course]:
if state[nxt] == GRAY:
return True # back edge → cycle
if state[nxt] == WHITE and has_cycle(nxt):
return True
state[course] = BLACK
return False
return not any(
state[c] == WHITE and has_cycle(c) for c in range(numCourses)
)
Walkthrough ([[1,0],[0,1]] → edges 0→1, 1→0): DFS from 0 marks 0 GRAY, visits 1, marks 1 GRAY, follows 1→0 and finds 0 is GRAY → cycle → returns True, so canFinish returns False.
Complexity: each node turns GRAY then BLACK once and each edge is examined once → O(V + E) time, O(V + E) space (graph + recursion stack).
Common pitfalls
- Reversing the edge direction.
[a, b] means “b before a,” so the edge is b → a; getting this backwards inverts the whole answer only in asymmetric graphs but silently passes symmetric tests.
- Using a plain
visited set instead of three colors in DFS: you can’t distinguish “still on the stack” (cycle) from “finished on another branch” (fine), producing false cycle reports.
- Forgetting isolated courses with no prerequisites — they start at in-degree 0 and must be counted as takeable.
- Hitting Python’s recursion limit on a long dependency chain (up to 2000 deep) with the DFS version; Kahn’s has no such issue.
Pattern takeaway
“Can all tasks with dependencies be completed?” is cycle detection on a directed graph, solved with topological sorting. Kahn’s in-degree BFS returns feasibility (and an order) with no recursion, while DFS three-coloring detects the back edge directly. Both are O(V + E); choose by whether you want an ordering or explicit stack structure.