Course Schedule II LeetCode 210 Guide

LeetCode 210 Course Schedule II gives you n courses labeled 0 to n-1 and a list of prerequisite pairs [a, b] meaning you must take course b before course a. Your task is not just to check whether all courses can be finished, but to return one valid ordering in which to take them all. If no valid ordering exists (a cycle is present), return an empty array.

This is a classic topological sort problem. A topological ordering of a directed graph is a linear arrangement of nodes such that for every directed edge u → v, node u appears before v in the sequence. Topological sort is only possible on directed acyclic graphs (DAGs) — the presence of a cycle means no such ordering can exist.

Understanding the output contract is important: any valid topological ordering is accepted. There may be multiple correct answers. You are not asked for the lexicographically smallest ordering or any specific one — just a valid sequence that respects all prerequisite constraints.

Course Schedule I (LeetCode 207) only asks whether you can finish all courses — a boolean feasibility check. Course Schedule II asks for the actual ordering. The good news: if you already understand Kahn's BFS solution for Course Schedule I, you are 90% of the way there. The only change is collecting the nodes as you dequeue them.

In Course Schedule I, you process each zero in-degree node, decrement its neighbors' in-degrees, and enqueue any that reach zero. You finish by checking whether the total processed count equals n. In Course Schedule II, every time you dequeue a node and process it, you append it to a result list. That result list is your topological order.

This tight relationship between the two problems is why they are often studied together. Mastering Kahn's algorithm with the order-collection extension gives you a template that handles both problems with minimal code change.

Kahn's algorithm works by repeatedly removing nodes with no incoming edges (in-degree zero) from the graph. These nodes have no prerequisites that haven't been satisfied yet, so they are safe to schedule next. After removing a node, you update the in-degrees of its neighbors, and any that reach zero become newly schedulable.

The BFS formulation uses a queue to track all currently zero in-degree nodes. You initialize the queue with every node that starts at in-degree zero. Then you process nodes one at a time: dequeue a node, add it to the result list, and for each of its outgoing neighbors, decrement their in-degree and enqueue them if they hit zero.

The process continues until the queue is empty. At that point, either every node has been processed and the result list contains a valid topological ordering, or some nodes were never enqueued because they remained in a cycle with persistent in-degrees above zero.

After Kahn's BFS completes, the cycle detection check is a single comparison: if the result list contains exactly n nodes, you processed every course and the result is a valid ordering. If the result list contains fewer than n nodes, some courses were never reachable because they were trapped in a cycle.

Nodes in a cycle always have in-degree greater than or equal to 1 even after all other nodes have been processed. Because the only way to enter the queue is to have in-degree zero, cycle members are permanently blocked. They never get dequeued, never get appended to the result, and the result length falls short of n.

This implicit cycle detection is one of the key advantages of Kahn's algorithm over DFS-based topological sort. There is no need to maintain an explicit visited / in-progress / done state. The in-degree arithmetic handles everything: if a node's in-degree never reaches zero, it is part of a cycle.

The DFS approach to topological sort uses three node states: unvisited (0), in-progress (1), and done (2). For each unvisited node, you run DFS. If you encounter an in-progress node during DFS, you have found a cycle. When DFS finishes a node (all its descendants are done), you append it to a result list.

After all DFS calls complete without detecting a cycle, you reverse the result list. The reversal is necessary because nodes are appended in post-order — a node is added after all its descendants. Reversing converts this to pre-order, which is the correct topological sequence (prerequisites before dependents).

Kahn's BFS is generally preferred for this problem because it naturally produces the order without a reversal step and the cycle check is a single length comparison. DFS is equally correct and also O(V+E), but requires careful state management with the three-color marking to avoid false cycle detections.

In Python, build an adjacency list and in-degree array with a single loop over prerequisites. Initialize a deque with all nodes at in-degree 0. Run the BFS loop: pop left, append to result, decrement neighbors, enqueue zeros. After the loop, return result if len(result) == numCourses else []. The full solution is about 15 lines.

In Java, use an ArrayList<List<Integer>> for the adjacency list and an int[] indegree array. Use ArrayDeque<Integer> for the BFS queue. The logic is identical to Python. The result is an int[] that you fill index by index as you dequeue nodes. Return the result array if the fill count equals numCourses, otherwise return new int[]{}.

Both implementations run in O(V+E) time where V = numCourses and E = prerequisites.length. Space complexity is also O(V+E) for the adjacency list plus O(V) for the in-degree array and queue. The space is dominated by the adjacency list representation of the graph.

Course Schedule II sits at the intersection of graph traversal and ordering problems. The topological sort pattern appears across a wide family of interview questions: anywhere you need to sequence tasks, courses, or events subject to dependency constraints, you are likely looking at a topological sort problem in disguise.

Alien Dictionary (LeetCode 269) constructs a character ordering from a sorted word list — topological sort on the derived character precedence graph. Course Schedule III (LeetCode 630) adds a greedy twist: given deadlines and durations, maximize the number of courses you can take using a max-heap greedy strategy. Minimum Height Trees (LeetCode 310) applies a leaf-pruning technique equivalent to topological sort from the outside in.

Mastering Kahn's algorithm with both the feasibility check (Course Schedule I) and the order-collection extension (Course Schedule II) gives you a reusable template. The pattern: build adjacency list + in-degrees, seed queue with zeros, BFS while collecting, validate length at the end. Recognize it and the family of problems becomes straightforward.