207. Course Schedule
On LeetCode ->Problem¶
Given courses numbered from 0 to numCourses - 1, each pair [course, prerequisite] requires completing prerequisite before course. Return whether all courses can be completed.
Courses absent from prerequisites can be taken freely.
numCourses = 5
prerequisites = [[1, 4], [2, 4], [3, 1], [3, 2]]
Order constraints: 4 -> 1 -> 3
4 -> 2 -> 3
Output: true
Key trick¶
Model the constraints as a directed graph and determine whether it is acyclic. Kahn's topological sort repeatedly completes courses with no remaining prerequisites.
Trap¶
A node visited earlier in a traversal does not imply a cycle. Multiple valid paths can converge on the same course, so DFS must distinguish nodes on the current path from fully processed nodes.
Why is it interesting?¶
It turns a scheduling question into directed-cycle detection and demonstrates the difference between graph reachability and dependency ordering.
Python solution¶
from collection import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]],) -> bool:
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, prerequisite in prerequisites:
# Completing prerequisite makes course available eventually.
graph[prerequisite].append(course)
indegree[course] += 1
# Courses with no unmet prerequisites can be completed immediately.
q = deque(course for course in range(numCourses) if indegree[course] == 0)
completed = 0
while q:
course = q.popleft()
completed += 1
for nxt in graph[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return completed == numCourses
def canFinish_2(self, numCourses: int, prerequisites: list[list[int]],) -> bool:
graph = TopologicalSorter()
for course in range(numCourses):
graph.add(course)
for course, prerequisite in prerequisites:
graph.add(course, prerequisite)
try:
tuple(graph.static_order())
return True
except CycleError:
return False
Time complexity: \(O(n + m)\), where \(n\) is the number of courses and \(m\) is the number of prerequisites.
Space complexity: \(O(n + m)\).
Comment on my solution¶
- Correctly models each prerequisite as a directed edge and identifies cycle detection as the real problem.
- The
visitedset contains every node reached during one traversal, not only nodes on the current path. - The failing example is a diamond-shaped DAG: course
3is reached through both1and2, so the second visit is incorrectly treated as a cycle. - Restarting DFS from every course can also take \(O(n(n + m))\) time.
- A course absent from all prerequisite pairs is independent and can always be taken.
- A DFS solution would require three states: unvisited, currently visiting, and fully processed.
# Wrong Answer: 45/54 testcases passed
# 5, [[1,4],[2,4],[3,1],[3,2]]
# output: False
# expected: True
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
# 2, [[1,0]] -> True
# 2, [[1,0],[0,1]] -> True
graph = [[] for _ in range(numCourses)]
for a, b in prerequisites:
graph[b].append(a)
# start DFS from every node looking for cycle
for course in range(numCourses):
visited = set()
stack = [course]
while stack:
course = stack.pop()
for next_course in graph[course]:
if next_course in visited:
return False
visited.add(next_course)
stack.append(next_course)
return True
Extra¶
First time I hear about Kahn's topological sort and it's not clear to me why we get the right answer in the first algorithm above.
1) What is Kahn's topological sort? 2) How it is applied in this problem?
What is Kahn's topological sort?¶
A topological order is an ordering of a directed graph where every node appears after all its prerequisites.
For example:
One valid topological order is:
Kahn's algorithm builds such an order by repeatedly removing nodes with indegree zero.
- A node's indegree is the number of incoming edges.
- In this problem, it is the number of prerequisites the course still needs.
- An indegree-zero course can be taken immediately.
The algorithm is:
- Count each node's indegree.
- Put all indegree-zero nodes in a queue.
- Remove a node from the queue.
- Remove its outgoing edges by decreasing its neighbors' indegrees.
- Add any neighbor whose indegree becomes zero to the queue.
- If every node was removed, there was no cycle.
Why does it detect a cycle?¶
Every finite directed acyclic graph has at least one node with indegree zero.
Intuitively, if every node had an incoming edge, you could keep following edges backward forever. Because the graph is finite, you would eventually revisit a node, which would form a cycle.
Therefore:
- If there are still courses left but none has indegree zero, those courses cannot be completed.
- At least some of them form a cycle.
- Other remaining courses may simply depend on that cycle.
For example:
Both nodes have indegree one:
The initial queue is empty, so no course can be processed.
How is it applied to Course Schedule?¶
For each prerequisite pair:
Create this directed edge:
For example:
becomes:
Course 1 has one unmet prerequisite, so its indegree is incremented.
The important parts of the algorithm are:
Here:
graph[prerequisite]contains courses unlocked by that prerequisite.indegree[course]counts the course's unmet prerequisites.
Initially, all courses with no prerequisites enter the queue:
When a course is completed, it satisfies one prerequisite for each dependent course:
If every course eventually enters the queue, all courses can be completed:
In this implementation, every course is added to q at most once, so its final length is the number of courses processed.
Walkthrough of the failing case from your solution¶
The graph is:
Initial indegrees are:
Initially available courses:
Processing course 4 removes one prerequisite from courses 1 and 2:
They are added to the queue:
Processing course 1 changes:
Processing course 2 changes:
Course 3 is now available:
All five courses were processed, so the answer is True.
The two paths reaching course 3 are not a cycle. They simply represent two prerequisites that must both be completed. Indegree counting handles that naturally.
Kahn's topological sort and BFS¶
Link between Kahn's topological sort and BFS?
If you mean Kahn's algorithm for topological sorting:
- Kahn's algorithm is essentially BFS-like, but instead of exploring by distance from a source, it processes nodes based on in-degree = 0.
- Start by putting all nodes with in-degree 0 into a queue.
- Repeatedly dequeue a node, add it to the topological order, and decrement the in-degree of its neighbors.
- Any neighbor whose in-degree becomes 0 is enqueued.
So the link is:
- BFS: queue + process neighbors
- Kahn: queue + process neighbors whose remaining in-degree becomes 0
Unlike ordinary BFS, Kahn's algorithm is specifically designed for DAGs and produces a topological ordering.
So Kahn's topological sorting is a class of BFS.
Yes—with a small qualification.
Kahn's topological sorting is BFS-like (queue-based), and is often described as a form of BFS. But it's not ordinary BFS because the rule for adding nodes to the queue is in-degree becoming 0, not “discovered from a visited node.”
So:
Kahn's algorithm ≈ BFS traversal framework + in-degree constraint → topological order.