Course Schedule II
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.
Unlike the yes/no version of this problem (Course Schedule, which only asks whether all courses can be finished), this problem requires producing the ordering itself. The cycle detection logic stays the same: if the graph contains a cycle, no valid ordering exists and we return an empty array.
Key Constraints:
numCourses <= 2000-> Small enough that any O(V + E) traversal runs comfortably.prerequisites.length <= n * (n - 1)-> The graph can have up to roughly 4 million edges. Both approaches below visit each edge once, so this is not a problem.ai != bi-> No self-loops, but cycles through multiple nodes are still possible.- All pairs are distinct -> No duplicate edges, so each edge contributes one to an in-degree count.
Approach 1: BFS Topological Sort (Kahn's Algorithm)
Intuition
A course with no prerequisites can be taken immediately. Taking it removes one dependency from every course that lists it as a prerequisite, which may make new courses available. Repeating this until no courses remain produces a valid ordering.
This is Kahn's algorithm. We track the in-degree of each node (how many prerequisites it still has) and start a BFS from all nodes with in-degree 0. Each time we process a node, we append it to the result and decrement the in-degree of its neighbors. When a neighbor's in-degree drops to 0, it joins the queue.
The output order is valid because a course only enters the queue once its in-degree reaches 0, and its in-degree only reaches 0 after every one of its prerequisites has been dequeued and placed earlier in the result. The same counter handles cycle detection: every node in a cycle has an incoming edge from another node in the cycle, so none of them ever reaches in-degree 0 and none is ever processed. If fewer than numCourses nodes end up in the result, a cycle exists and we return an empty array.
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
Take numCourses = 4 and prerequisites = [[1,0],[2,0],[3,1],[3,2]]. The edges are 0 -> 1, 0 -> 2, 1 -> 3, and 2 -> 3, so course 0 unlocks courses 1 and 2, and course 3 needs both.
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).
Kahn's algorithm builds the ordering from the front. The other standard technique, DFS with post-order, builds it from the back: a course is recorded only after every course that depends on it has been recorded.
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.
With only visited/unvisited, the DFS cannot tell the difference between reaching a node on the current recursion path (a back edge, which means a cycle) and reaching a node that was fully explored in an earlier branch (a cross edge, which is harmless). The In-progress state marks the nodes on the current path, so encountering one means the path loops back on itself.
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
Same input as before: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. The DFS starts at node 0, descends as deep as it can, and records each node when it finishes. Reversing the recorded order gives the answer, [0,2,1,3], which differs from the BFS result but is equally valid.
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); the recursion can reach numCourses frames on a single long prerequisite chain.