This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#210) before relying on it.

Course Schedule II

An interactive visualization of Kahn's BFS topological sort. Watch how in-degree tracking processes courses in dependency order, and how cycles are detected when not all courses can be scheduled.

Topological Sort LeetCode 210 ↗ Medium

The Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses (a cycle exists), return an empty array.

Interactive Visualization

Num Courses

Prerequisites (pairs: a,b means b→a)

Preset

Speed:

Directed Acyclic Graph (DAG)

Queue & Result

Queue:

Empty

Order:

[]

Code

fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {    val graph = Array(numCourses) { mutableListOf<Int>() }    val inDegree = IntArray(numCourses)    for ((course, prereq) in prerequisites) {        graph[prereq].add(course)        inDegree[course] += 1    }    val queue: ArrayDeque<Int> = ArrayDeque()    for (i in 0 until numCourses) {        if (inDegree[i] == 0) {            queue.add(i)        }    }    val order = mutableListOf<Int>()    while (queue.isNotEmpty()) { val node = queue.removeFirst()        order.add(node)        for (neighbor in graph[node]) {            inDegree[neighbor] -= 1            if (inDegree[neighbor] == 0) {                queue.add(neighbor)            }        }    }    return if (order.size == numCourses) order.toIntArray() // success           else intArrayOf()  // cycle detected}

def findOrder(numCourses, prerequisites):    graph = [[] for _ in range(numCourses)]    in_degree = [0] * numCourses    for course, prereq in prerequisites:        graph[prereq].append(course)        in_degree[course] += 1    queue = deque()    for i in range(numCourses):        if in_degree[i] == 0:            queue.append(i)    order = []    while queue:        node = queue.popleft()        order.append(node)        for neighbor in graph[node]:            in_degree[neighbor] -= 1            if in_degree[neighbor] == 0:                queue.append(neighbor)    if len(order) == numCourses:        return order    return []  # cycle detected

Status

Press Step or Play to begin.

How It Works

Key Insight

Course prerequisites form a directed graph. Finding a valid ordering is exactly the topological sort problem: arrange vertices so that for every directed edge u→v, u comes before v. This is only possible if the graph has no cycles (i.e., it is a DAG).

Kahn's BFS Algorithm

Kahn's algorithm uses in-degree tracking. The in-degree of a node is the number of edges pointing into it — the number of prerequisites it has. A course with in-degree 0 has no unmet prerequisites and can be taken immediately.

Build the graph: Create an adjacency list and compute in-degrees from the prerequisites.
Initialize the queue: Add all courses with in-degree 0 (no prerequisites).
Process the queue: Dequeue a course, add it to the result order, then for each neighbor, decrement its in-degree. If a neighbor's in-degree drops to 0, enqueue it.
Cycle detection: If the result contains fewer courses than numCourses, a cycle exists — some courses have circular dependencies that can never be resolved.

Why It Works

At every step, we only process courses whose prerequisites have all been completed (in-degree = 0). Removing a processed course from the graph reduces the in-degrees of its dependents, potentially freeing them up. If a cycle exists, the nodes in the cycle never reach in-degree 0, so they are never enqueued — giving us a clean way to detect impossible schedules.

Complexity

Time O(V + E)

Space O(V + E)

Where V is the number of courses and E is the number of prerequisite pairs. Each node and edge is processed exactly once. The adjacency list and in-degree array together use O(V + E) space.