Example 1
ready- Input
numCourses = 2 prerequisites = [ [ 1, 0 ] ]- Expected
true- Why
- take course 0, then course 1
Course Schedule
35 min · canFinish()mediumOpen in LeetCode #207 ↗
A study plan can fail before the semester begins: Course A needs B, B needs C, and C quietly needs A. No first course exists.
You're given numCourses courses labeled from 0 through numCourses - 1 and a list
prerequisites. A pair [course, prerequisite] means you must finish prerequisite
before taking course.
Return true if you can finish every course, or false if the requirements contain a
cycle — a dependency chain that leads back to its starting course. Each pair is a
directed edge, a one-way dependency from the prerequisite to the course. Separate
groups of courses are allowed, and a course may require nothing.
Constraints
1 <= numCourses <= 2_0000 <= prerequisites.length <= 5_000- Every pair contains two course labels in the range
0..numCourses - 1. - Prerequisite pairs are distinct, and no course is its own prerequisite.
Hints
Name the failure
The schedule is impossible exactly when the directed graph contains a cycle. A DFS can detect an edge back to a course still on the current path.
Find what can start now
Count each course's unmet prerequisites. Any course with a count of zero is ready immediately.
Consume the plan
Take a ready course, reduce the counts of courses that depend on it, and enqueue any count that reaches zero. You succeed only if this process consumes every course.
Follow-up
Can you extend your solution to return one concrete course order when the plan is possible, and return an empty array otherwise?
Visible cases
Examples
Example 2
ready- Input
numCourses = 2 prerequisites = [ [ 1, 0 ], [ 0, 1 ] ]- Expected
false- Why
- each course waits for the other
Example 3
ready- Input
numCourses = 1 prerequisites = []- Expected
true- Why
- one course with no prerequisite is immediately finishable
Interview signal
Asked at
AmazonGoogleMeta
DFS cycle check — track the current path
The DFS cycle check uses three colors for each course:
0means unvisited.1means active on the current search path.2means fully checked and safe.
An edge to an active course closes a directed cycle. The iterative stack below stores the next neighbor to inspect, so it handles a chain of 2,000 courses without depending on Python's recursion limit.
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(num_courses)]
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
color = [0] * num_courses
for start in range(num_courses):
if color[start] != 0:
continue
color[start] = 1
stack = [(start, 0)]
while stack:
course, next_index = stack[-1]
if next_index == len(graph[course]):
color[course] = 2
stack.pop()
continue
next_course = graph[course][next_index]
stack[-1] = (course, next_index + 1)
if color[next_course] == 1:
return False
if color[next_course] == 0:
color[next_course] = 1
stack.append((next_course, 0))
return TrueTime O(V + E), space O(V + E) — every course and dependency is processed once, including the adjacency list and explicit DFS stack.
Kahn's topological sort — repeatedly take a ready course
A topological order places every prerequisite before the course that needs it. Kahn's topological sort builds such an order from courses whose in-degree — number of incoming prerequisite edges — is zero.
Take one ready course and remove its outgoing dependencies. Each dependent course whose
in-degree falls to zero becomes ready. A cycle leaves some courses with positive
in-degree forever, so the processed count finishes below num_courses.
from collections import deque
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(num_courses)]
in_degree = [0] * num_courses
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
in_degree[course] += 1
ready = deque(
course for course in range(num_courses) if in_degree[course] == 0
)
completed = 0
while ready:
course = ready.popleft()
completed += 1
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
ready.append(next_course)
return completed == num_coursesTime O(V + E), space O(V + E) for the graph, in-degree array, and queue.
DFS proves that no dependency points back into the current path. Kahn's algorithm proves that every course can eventually become ready. They're two views of the same acyclic graph.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite