Course Schedule II
Last Updated: April 5, 2026
Understanding the Problem
We have a set of courses numbered 0 to numCourses - 1, and some prerequisite relationships between them. The pair [a, b] means "you must take course b before course a." We need to find an ordering where every course appears after all of its prerequisites. If no such ordering exists (because there is a circular dependency), we return an empty array.
This is the classic topological sort problem. The courses are nodes in a directed graph, and each prerequisite [a, b] creates an edge from b to a (meaning b must come before a). A topological sort gives us a linear ordering of nodes such that for every directed edge u -> v, node u appears before node v.
The critical twist compared to Course Schedule I (which just asks "is it possible?") is that we need to actually produce the ordering, not just check for cycles. But the cycle detection logic is the same: if the graph has a cycle, no valid ordering exists.
Key Constraints:
numCourses <= 2000-> With up to 2,000 nodes, O(n^2) algorithms are fine. O(n + e) graph traversals are very comfortable.prerequisites.length <= n * (n - 1)-> The graph can have up to ~4 million edges in the worst case. Standard BFS/DFS handles it since we visit each edge once.ai != bi-> No self-loops, but cycles involving multiple nodes are possible.- All pairs are distinct -> No duplicate edges to worry about.
Approach 1: BFS Topological Sort (Kahn's Algorithm)
Intuition
The most intuitive way to think about this: which courses can I take right now? Any course with zero prerequisites can be taken immediately. Once I take those courses, some new courses might become available because their prerequisites are now satisfied. I keep picking available courses until either I have taken them all (success) or no more courses are available but some remain (cycle detected).
This is exactly Kahn's algorithm. We track the in-degree of each node (how many prerequisites it still has). We start a BFS from all nodes with in-degree 0. Each time we process a node, we "remove" it from the graph by decrementing the in-degree of its neighbors. When a neighbor's in-degree drops to 0, it joins the queue.
The beauty of this approach is that it naturally detects cycles. If there is a cycle, the nodes in the cycle will never reach in-degree 0, so they will never be processed. At the end, if the number of processed nodes is less than numCourses, we know a cycle exists.
Kahn's algorithm works because it simulates the process of "peeling off" layers of the graph. At each step, we remove nodes with no remaining dependencies (in-degree 0). These nodes are safe to place next in the ordering because nothing needs to come before them that has not already been placed. By repeatedly removing these nodes and updating in-degrees, we process the entire graph layer by layer.
The cycle detection falls out naturally. In a cycle, every node depends on at least one other node in the cycle. None of them can ever reach in-degree 0, so they are never added to the queue.
Algorithm
- Build an adjacency list from the prerequisites. For each
[a, b], add an edge from b to a. - Compute the in-degree of every node.
- Initialize a queue with all nodes that have in-degree 0.
- While the queue is not empty, dequeue a node, add it to the result, and decrement the in-degree of all its neighbors. If any neighbor's in-degree becomes 0, enqueue it.
- If the result contains all numCourses nodes, return it. Otherwise, return an empty array (cycle detected).
Example Walkthrough
Code
- Time Complexity: O(V + E). Building the graph takes O(E). The BFS visits each node once and each edge once. Total: O(V + E).
- Space Complexity: O(V + E). The adjacency list takes O(V + E). The in-degree array and queue take O(V).
Both approaches have the same asymptotic complexity, but there is a fundamentally different technique worth knowing: DFS-based topological sort. Instead of peeling layers from the front, what if we built the ordering from the back by finishing the deepest nodes first?
Approach 2: DFS Topological Sort
Intuition
Instead of figuring out what to take first, figure out what to take last. If you do a DFS and fully explore a node (visit all its descendants), then by the time you finish that node, all courses that depend on it have already been explored. So if you record nodes in the order they finish, and then reverse that order, you get a valid topological sort.
For cycle detection, we use three states for each node: Unvisited (not yet explored), In-progress (currently being explored), and Visited (fully explored). If during DFS we encounter a node that is in-progress, we have found a back edge, which means there is a cycle.
In a DFS, a node finishes after all of its descendants finish. So in post-order (the order nodes finish), a node always appears after its descendants. Reversing this gives us a topological order where a node appears before its descendants, which is exactly what we want.
The three-state system is the standard technique for detecting back edges in a directed graph. A back edge from a node to an in-progress ancestor means we have found a cycle. If we only used two states (visited/unvisited), we could not distinguish between a back edge (cycle) and a cross edge (no cycle).
Algorithm
- Build an adjacency list from the prerequisites.
- Create a state array initialized to Unvisited for all nodes.
- For each unvisited node, run DFS.
- In DFS: mark the node as In-progress. For each neighbor, if it is In-progress, a cycle exists. If it is Unvisited, recurse. After processing all neighbors, mark the node as Visited and add it to the result list.
- Reverse the result list. If no cycle was detected, return it. Otherwise, return an empty array.
Example Walkthrough
Code
- Time Complexity: O(V + E). Building the graph takes O(E). The DFS visits each node once and each edge once. Reversing the result takes O(V). Total: O(V + E).
- Space Complexity: O(V + E). The adjacency list takes O(V + E). The state array and recursion stack take O(V).