LeetCode Course Schedule: Topological Sort with DFS

LeetCode 207, Course Schedule, is the canonical interview problem for directed graph cycle detection. The variant LeetCode 210 asks you to return a valid ordering, which is a small extension of the same algorithm. Together they are some of the highest-frequency graph problems in technical interviews, so the algorithmic template is worth memorizing exactly.

The Problem

There are numCourses courses labeled 0 to numCourses - 1. You are given a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return True if you can finish all courses, otherwise False.

Example inputs and outputs:

Input:  numCourses = 2, prerequisites = [[1, 0]]
Output: True
Explanation: Take 0, then 1.

Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False
Explanation: 0 and 1 depend on each other -> cycle.

Input:  numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]]
Output: True
Explanation: Take 0, 1, 2, 3.

This is “is the directed graph a DAG?” If the graph has any cycle, the answer is False; otherwise a valid order exists. Both DFS and BFS solve it; DFS with three-color marking is the classic exposition.

Brute Force

The brute force is to try every ordering of courses and check feasibility. That is O(n!), which is unusable for anything past n = 10.

from itertools import permutations

def can_finish_brute(num_courses: int, prerequisites: list[list[int]]) -> bool:
    for order in permutations(range(num_courses)):
        position = {c: i for i, c in enumerate(order)}
        if all(position[b] < position[a] for a, b in prerequisites):
            return True
    return False

Useful only for a sanity check on tiny inputs.

Optimal Solution

DFS with three-color marking. Each node is in one of three states:

• 0 = unvisited
• 1 = currently on the DFS stack (gray)
• 2 = fully processed (black)

If DFS reaches a gray node, there is a back edge, which means a cycle.

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[b].append(a)

    state = [0] * num_courses

    def dfs(node: int) -> bool:
        if state[node] == 1:
            return False
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = 2
        return True

    for course in range(num_courses):
        if not dfs(course):
            return False
    return True

An equivalent Kahn algorithm version uses BFS over in-degrees:

from collections import deque

def can_finish_kahn(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indeg[a] += 1

    queue = deque(c for c in range(num_courses) if indeg[c] == 0)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses

Both are O(V + E). Kahn is slightly easier to extend to “return a valid order” because the queue produces one as it runs.

Walk Through an Example

Take numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]].

Adjacency list (edges from prereq to course):

0 -> [1]
1 -> [2]
2 -> [3]
3 -> []

DFS starting from 0:

visit 0  state[0] = 1
  visit 1  state[1] = 1
    visit 2  state[2] = 1
      visit 3  state[3] = 1
      state[3] = 2
    state[2] = 2
  state[1] = 2
state[0] = 2

No gray-on-gray collision, so return True.

For the cyclic case [[1, 0], [0, 1]], DFS from 0 visits 1, which tries to visit 0 again while state[0] == 1. Return False.

Edge Cases

• Empty prerequisites: every ordering works; return True.
• Self-prerequisite, such as [1, 1]: this is a self-loop and a cycle; return False.
• Disconnected components: the outer loop covers every starting node, so disconnected subgraphs are handled.
• Duplicate prerequisite entries: the algorithm is robust because revisited black nodes return early.
• Large numCourses with sparse prereqs: O(V + E) handles it.
• Recursion depth: Python defaults to 1000; for very deep chains, either raise the limit or use the Kahn BFS version.

Complexity Analysis

• Time: O(V + E) where V = numCourses and E = len(prerequisites). Each node and edge is processed a constant number of times.
• Space: O(V + E) for the adjacency list and O(V) for the state array. Recursion stack is O(V) in the worst case.

If you want to ground the V plus E intuition more carefully, see /blog/big-o-notation-explained.

How to Explain It in an Interview

Use this script:

1. Translate the problem into graph language: nodes are courses, edges are prerequisite-to-course.
2. State the goal: detect a cycle in the directed graph.
3. Choose DFS three-color marking. Explain the three states and why gray-on-gray is the signature of a back edge.
4. Mention Kahn as the BFS alternative and note that it extends naturally to producing an ordering (LeetCode 210).
5. State complexity as O(V + E) for both.
6. Trace a small cyclic example to prove the cycle detection works.

A common follow-up: “Now return the order.” Switch to Kahn and emit nodes as they leave the queue.

Related Problems

• Course Schedule II (LeetCode 210): return a valid order, not just feasibility.
• Alien Dictionary (LeetCode 269): build the graph from word ordering, then topological sort.
• Minimum Height Trees (LeetCode 310): BFS peeling of leaves, conceptually related.
• Find Eventual Safe States (LeetCode 802): cycle detection variant.
• For more traversal patterns see /blog/graphs-bfs-and-dfs.

Wrap up

Course Schedule is the cleanest interview check for whether you can build a graph from input, choose between DFS and BFS thoughtfully, and reason about cycles. Memorize the three-color DFS template and the Kahn BFS template, and know which extends to which follow-up. After this, see /blog/graphs-introduction for the broader vocabulary and /blog/graphs-bfs-and-dfs for the traversal mechanics you will reuse across most graph problems in interviews.