Course Schedule II

Problem Given numCourses and prerequisite pairs [a, b] (b before a), return a valid order to take all courses, or [] if impossible.

Input / Output

• Input: int numCourses, int[][] prerequisites. Output: valid ordering or [].

Constraints

• Up to 2000 courses / 5000 edges; O(V + E) expected.

Example

• numCourses = 4, prereqs = [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3] or [0,2,1,3].

Expected approach

• Topological sort. Kahn's: build adjacency + indegrees; queue all indegree-0 nodes; pop-append-decrement; if the output covers all courses it's the order, else a cycle exists — the count check IS the cycle detection. DFS alternative: post-order reversed, with three colors to detect back edges. Both O(V+E). Know both and the cycle-reporting difference; Course Schedule I (just feasibility) and lexicographically-smallest order (priority queue in Kahn's) are the adjacent variants.