Course Schedule

Interview Prep

StandardGraphsgraphstopological-sortcycle-detection

The problem

You have num_courses courses labeled 0..num_courses-1. Some courses have prerequisites: [a, b] means you must take course b before course a. Decide whether you can finish all courses. (Equivalently: does the directed prerequisite graph have a cycle?)

Pattern: cycle detection in a DAG

A valid course ordering exists if and only if the prerequisite graph is a directed acyclic graph (DAG) — a cycle would mean some course is a (transitive) prerequisite of itself, which is impossible. Two textbook approaches: DFS with three-color marking detects back edges (= cycles), or Kahn's algorithm tries to peel off zero-indegree vertices and fails if any are left.

Both produce the topological order as a side effect if needed. The interviewer asks "can you finish" but the same code answers "what order should you take them in" with a one-line change.

Approach 1: DFS with three colors

Color each vertex WHITE (unvisited), GRAY (currently on the DFS stack), BLACK (fully processed). If a DFS edge ever points to a GRAY vertex, you've found a back edge — a cycle. 

def can_finish_dfs(num_courses: int, prereq: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    for a, b in prereq:
        graph[b].append(a)        # b must come before a

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses

    def visit(u: int) -> bool:
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return False              # back edge — cycle
            if color[v] == WHITE and not visit(v):
                return False
        color[u] = BLACK
        return True

    return all(color[u] == BLACK or visit(u) for u in range(num_courses))

Approach 2: Kahn's algorithm (BFS-style)

Maintain in-degree counts. Repeatedly "complete" any course with zero remaining prerequisites; each completion decrements the in-degree of its dependents. If every course is eventually completed, the graph is acyclic; if some are left with positive in-degree, they're inside a cycle. 

from collections import deque

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

    q = deque(u for u in range(num_courses) if indeg[u] == 0)
    completed = 0
    while q:
        u = q.popleft()
        completed += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return completed == num_courses

Trace (acyclic case)

num_courses = 4
prereq = [[1, 0], [2, 1], [3, 2]]   # 0 → 1 → 2 → 3 (linear chain)

graph = [[1], [2], [3], []]
indeg = [0, 1, 1, 1]

Initial queue: [0]
Step 1: pop 0, completed=1, decrement indeg of [1] → indeg=[0,0,1,1], queue=[1]
Step 2: pop 1, completed=2, decrement indeg of [2] → indeg=[0,0,0,1], queue=[2]
Step 3: pop 2, completed=3, decrement indeg of [3] → indeg=[0,0,0,0], queue=[3]
Step 4: pop 3, completed=4, no neighbors, queue=[]
return completed == 4 → True

Trace (cyclic case)

num_courses = 2
prereq = [[1, 0], [0, 1]]   # 0 → 1 → 0  (cycle)

graph = [[1], [0]]
indeg = [1, 1]

Initial queue: [] (no zero-indegree vertices)
Loop never executes. completed = 0.
return 0 == 2 → False

Complexity

Variations worth knowing