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.

mediumQ122 of 227 in Data Structures & Algorithms Est. time: 6 minsLast updated: July 2026

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

Course schedule feasibility with Kahn’s algorithm

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_courses

Follow-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?

2. What does Kahn’s algorithm produce as a byproduct of cycle detection?

3. What is the time complexity of solving course schedule with Kahn’s algorithm?

Flash Cards

1 / 4

Course Schedule Problem: How Would You Solve It?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Build the dependency graph

Seed the queue with zero-in-degree nodes

Process and reduce in-degrees

Compare processed count to total