LeetCode · #210

Course Schedule II Solution

Given numCourses and prerequisites, return a valid order to finish all courses — or an empty array if impossible due to a cycle.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #210

🏗️

Pattern

Graph — topological sort (ordering)

There are numCourses courses labeled 0 to numCourses-1. Given prerequisites [a, b] (must take b before a), return any valid course ordering. Return an empty array if no such ordering exists (cycle detected).

Example

 Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] // or [0,2,1,3] — any valid topological order 

Constraints

 • 1 ≤ numCourses ≤ 2000 • 0 ≤ prerequisites.length ≤ 5000 • prerequisites[i].length == 2,  a ≠ b • No duplicate prerequisite pairs 

Section Two · Approach 1

DFS Post-order — O(V+E)

Run DFS on every node. After fully exploring all outgoing edges of a node (post-order), push it to a stack. If a cycle is detected (back edge — node in "visiting" state), return empty. The stack reversed gives the topological order.

Why post-order gives topological order

In DFS, a node is pushed to the stack only after all courses it leads to have been pushed. So when you pop the stack, everything that needs to come before a course appears earlier in the list. Reversing the push order gives correct prerequisites-first ordering.

Why Kahn's BFS is often clearer

Trade-off: DFS post-order requires careful 3-color state tracking and the stack reversal can be confusing. Kahn's BFS builds the order directly front-to-back: courses dequeued first (lowest in-degree = no remaining prerequisites) appear earliest in the result — no reversal needed, no separate stack.

Java — DFS post-order topological sort

 import java.util.*;
class Solution {
public int[] findOrder(int n, int[][] pre) {
List<List<Integer>> adj = new ArrayList<>();
for (int i=0; i<n; i++) adj.add(new ArrayList<>());
for (int[] p : pre) adj.get(p[1]).add(p[0]);
int[] state = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i=0; i<n; i++)
if (hasCycle(adj, state, i, stack)) return new int[0];
int[] res = new int[n];
for (int i=0; i<n; i++) res[i] = stack.pop();
return res;
    }
private boolean hasCycle(List<List<Integer>> adj, int[] st, int v, Stack<Integer> stk) {
if (st[v]==1) return true;
if (st[v]==2) return false;
        st[v]=1;
for (int nb : adj.get(v))
if (hasCycle(adj,st,nb,stk)) return true;
        st[v]=2; stk.push(v); // post-order push return false;
    }
}

Python — DFS post-order

 class Solution:
def findOrder(self, n: int, prerequisites: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(n)]
for a, b in prerequisites: adj[b].append(a)
        state, order = [0]*n, []
def dfs(v):
if state[v]==1: return False if state[v]==2: return True
state[v]=1 if not all(dfs(nb) for nb in adj[v]): return False
state[v]=2; order.append(v)
return True if not all(dfs(i) for i in range(n)): return []
return order[::-1]

Metric	Value
Time	O(V + E)
Space	O(V + E) adjacency + O(V) state + O(V) call stack

Section Three · Approach 2

Kahn's BFS — O(V+E)

Build in-degree counts. Enqueue all zero-in-degree nodes. Dequeue a node, append it to the result order, then decrement neighbors' in-degrees — enqueuing any that reach zero. If all nodes are processed, return the order; otherwise a cycle exists.

💡 Mental model: Imagine releasing courses one-by-one in a university registration system. Only courses with no remaining prerequisites can open. When a course opens, you "complete" it and remove it as a prerequisite for future courses. Any course whose prerequisite count drops to zero becomes immediately available. The order in which courses open is a valid course completion order. If some courses never open (their count never hits zero), a circular dependency blocks them.

Algorithm — Kahn's BFS (produces ordering directly)

Build adj[b] → [a, ...] and inDegree[a] for each prerequisite [a, b].
Enqueue all nodes with inDegree == 0.
BFS: dequeue node v, append to order[], decrement in-degree of each neighbor, enqueue if 0.
If order.length == n, return order; else return [].

🎯 When to recognize this pattern:

"Return the ordering" (not just yes/no) always calls for Kahn's BFS.
Kahn's builds the order while processing, whereas DFS builds it in reverse and requires a flip.
You'll use this in LC 207 (just check count), LC 329 (Longest Increasing Path in Matrix — DFS variant), and any build system / package manager dependency resolver.

Kahn's vs DFS for topological sort:

Kahn's BFS guarantees a valid left-to-right ordering by construction — no reversal needed.
DFS post-order requires reversing the output. In interviews, Kahn's is easier to explain intuitively.
DFS is more elegant for pure cycle detection (LC 207).

Section Four · Trace

Visual Walkthrough

Trace Kahn's BFS on n=4, prerequisites [[1,0],[2,0],[3,1],[3,2]].

Course Schedule II — Kahn's BFS Topological Ordering

Section Five · Implementation

Code — Java & Python

Java — Kahn's BFS topological sort

 import java.util.*;
class Solution {
public int[] findOrder(int n, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDeg = new int[n];
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            inDeg[p[0]]++;
        }
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++)
if (inDeg[i] == 0) q.offer(i);
int[] order = new int[n];
int idx = 0;
while (!q.isEmpty()) {
int v = q.poll();
            order[idx++] = v; // add to result in BFS order for (int nb : adj.get(v))
if (--inDeg[nb] == 0) q.offer(nb);
        }
return idx == n ? order : new int[0]; // cycle → not all processed
}
}

Python — Kahn's BFS topological sort

 from collections import deque
class Solution:
def findOrder(self, n: int, prerequisites: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(n)]
        in_deg = [0] * n
for a, b in prerequisites:
            adj[b].append(a)
            in_deg[a] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
        order = []
while q:
            v = q.popleft()
            order.append(v)
for nb in adj[v]:
                in_deg[nb] -= 1 if in_deg[nb] == 0:
                    q.append(nb)
return order if len(order) == n else []

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force ordering (try all)	O(V!)	O(V)	Completely infeasible
DFS post-order	O(V + E)	O(V + E)	Needs reversal; recursive stack risk for large V
Kahn's BFS ← optimal	O(V + E)	O(V + E)	Builds order directly; iterative; intuitive explanation

LC 207 vs LC 210:

LC 207 asks "does a valid order exist?" — Kahn's check is processed == n.
LC 210 asks "what is the order?" — same algorithm, just collect the dequeued nodes into order[] and return it (or [] on cycle).
The code differs by only 2 lines.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No prerequisites	`n=3, []`	All in-degrees 0 → all enqueued immediately → order=[0,1,2]. Any ordering valid.
Single course	`n=1, []`	Return `[0]`.
Linear chain	`[[1,0],[2,1],[3,2]]`	Only one valid order: `[0,1,2,3]`. BFS enqueues each in sequence.
Cycle present	`[[1,0],[0,1]]`	Both have in-degree 1. Queue empty at start. order=[] returned.
Multiple valid orders	Diamond shaped	BFS may return either valid order — both are accepted. Problem says "any" valid order.
Reversed edge direction	`[a, b]` added as a→b	In-degree calculation breaks — b should gain +1 not a. See mistake box.

⚠ Common Mistake: Building the adjacency list as adj[a].add(b) instead of adj[b].add(a) for prerequisite [a, b] (b must come before a). This reverses all edges. The resulting "topological order" would have courses scheduled after their dependents — producing an invalid ordering. Remember: the edge in the dependency graph goes from prerequisite to dependent, i.e., from b to a.

← Back to Graph problems

LearningTree

LC 210 · Course Schedule II — Solution & Explanation | DSA Guide