Course Schedule Problem: How Would You Solve It?
Learn how to solve the course schedule problem with topological sort and cycle detection using DFS or Kahn’s algorithm.
Expected Interview Answer
Course schedule is a cycle-detection problem on a directed graph where each course is a node and a prerequisite relationship is a directed edge, and all courses can be completed if and only if that graph has no cycle, which you can verify with either DFS using three-color marking or Kahn's algorithm using topological sort via in-degree tracking.
In the DFS approach, each node is colored white (unvisited), gray (currently on the recursion stack), or black (fully processed); encountering a gray node during traversal means the current path has looped back on itself, which is a cycle, so scheduling is impossible. In Kahn's algorithm, you compute the in-degree of every course, seed a queue with all zero-in-degree courses, and repeatedly remove a course from the queue, decrement its neighbors' in-degrees, and enqueue any neighbor that drops to zero; if the number of processed courses at the end equals the total number of courses, there is no cycle and a valid ordering exists, otherwise a cycle blocks some courses from ever reaching zero in-degree. Both approaches run in O(V + E) time and O(V + E) space for the adjacency list and auxiliary tracking structures. Kahn's algorithm has the practical advantage of directly producing a valid course ordering as a byproduct, which is exactly what the related “Course Schedule II” variant asks for.
- O(V + E) time and space using either DFS or Kahn’s algorithm
- Kahn’s algorithm produces a valid topological order as a byproduct
- Three-color DFS marking cleanly distinguishes back edges from cross/forward edges
- Directly generalizes to build-dependency and task-scheduling systems
AI Mentor Explanation
Course schedule is like checking whether a set of net-practice rotation rules can all be honored, where each rule says one drill must happen before another, forming a directed dependency graph. Using Kahn's approach, a coach starts with drills that have no prerequisite drills at all, runs them, then frees up any drill whose only prerequisite was just completed, repeating until either all drills run or some drills never become eligible because they are stuck waiting on each other in a loop. That stuck situation is a cycle: drill A needs drill B, which needs drill A, which is logically impossible to schedule at all. If every drill eventually gets freed and run, the whole rotation is schedulable, and the order in which drills were freed is a valid practice sequence.
Step-by-Step Explanation
Step 1
Build the dependency graph
Add a directed edge from each prerequisite course to the course that depends on it, and track each node’s in-degree.
Step 2
Seed the queue with zero-in-degree nodes
Every course with no remaining prerequisites can start immediately; enqueue all of them.
Step 3
Process and reduce in-degrees
Dequeue a course, mark it processed, and decrement the in-degree of each course that depends on it; enqueue any that reach zero.
Step 4
Compare processed count to total
If the processed count equals the total number of courses, no cycle exists and scheduling is possible; otherwise a cycle blocks completion.
What Interviewer Expects
- Frame the problem explicitly as cycle detection on a directed graph
- Explain both DFS three-color marking and Kahn’s in-degree approach
- State O(V + E) time and space complexity
- Mention Kahn’s algorithm also yields a valid topological order as a byproduct
Common Mistakes
- Using an undirected-graph cycle check, ignoring edge direction
- Forgetting to reset or properly track the recursion-stack color in DFS, causing false cycle reports
- Not comparing the processed-node count to total node count as the final check in Kahn’s algorithm
- Confusing "course schedule" (feasibility, boolean) with "course schedule II" (produce the actual order)
Best Answer (HR Friendly)
“I model this as a directed graph of prerequisites and check for cycles, since a cycle means courses depend on each other in a loop and can never be scheduled. I usually reach for Kahn's algorithm, repeatedly removing courses with no remaining prerequisites, because it both detects cycles and gives me a valid course order for free.”
Code Example
from collections import deque
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return processed == num_coursesFollow-up Questions
- How would you modify this to return a valid course ordering instead of just a boolean?
- How would you detect and report which specific courses are part of a cycle?
- How does this differ from finding a cycle in an undirected graph?
- How would you solve this using DFS with three-color marking instead of Kahn’s algorithm?
MCQ Practice
1. What condition makes it impossible to complete all courses?
A cycle means a set of courses depend on each other in a loop, making it logically impossible to satisfy every prerequisite.
2. What does Kahn’s algorithm produce as a byproduct of cycle detection?
Processing zero-in-degree nodes in order naturally yields a valid topological ordering when no cycle exists.
3. What is the time complexity of solving course schedule with Kahn’s algorithm?
Every vertex and edge is processed exactly once across the in-degree computation and queue processing, giving O(V + E).
Flash Cards
What graph problem is course schedule, fundamentally? — Cycle detection on a directed graph of prerequisite relationships.
What does a gray node encountered during DFS indicate? — A back edge to a node on the current recursion stack, meaning a cycle exists.
What does Kahn’s algorithm give you besides a yes/no cycle answer? — A valid topological order of the courses, as a byproduct of the processing order.
What is the time and space complexity of both approaches? — O(V + E) time and O(V + E) space for the adjacency list and tracking structures.