Practice Course Schedule II
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Course Schedule II
Problem Statement
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Source: Course Schedule II on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
numCourses = 2, prerequisites = [[1,0]]
[0,1]
# Example 2
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
[0,2,1,3]
# Example 3
numCourses = 1, prerequisites = []
[0]
Constraints
How to solve Course Schedule II
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Prerequisites form a directed graph, and a valid course order is a topological ordering of it; repeatedly taking a course with no unmet prerequisites (Kahn's algorithm) builds the order and exposes a cycle when courses are left over.
Why brute force is not enough
Testing every permutation of courses against the prerequisite list is factorial time, impossible for numCourses up to 2000; rescanning all pairs each round to find a takeable course is O(numCourses * prerequisites), too slow when prerequisites.length can reach about 4 * 10^6.
Approach
- Build an adjacency list where each pair [a, b] adds a directed edge from b to a, and record each course's in-degree, the number of prerequisites it still needs.
- Seed a ready collection with every course whose in-degree is zero; a queue or a stack both work, since any such course is safe to take next.
- Repeatedly remove a ready course, append it to the order, and decrement the in-degree of each dependent course, adding any that reach zero. The invariant is that every emitted course has all its prerequisites earlier in the order.
- When the collection empties, return the order if its length equals numCourses; otherwise the leftover courses lie on a cycle, so return an empty array.
Walkthrough of Example 2
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → [0,2,1,3]
- Edges are 0 to 1, 0 to 2, 1 to 3, and 2 to 3; in-degrees are 0, 1, 1, 2 for courses 0 through 3.
- Only course 0 is ready. Using a stack as the ready collection, take 0, giving order [0], and decrement courses 1 and 2 to zero, pushing 1 then 2.
- Take 2 from the top, giving [0,2]; course 3 drops from 2 to 1.
- Take 1, giving [0,2,1]; course 3 drops to 0 and is pushed.
- Take 3, giving [0,2,1,3]. All 4 courses were emitted, so return [0,2,1,3]; a FIFO queue would give [0,1,2,3], also valid.
Time and space
Time O(V + E) · Space O(V + E). V is numCourses and E is prerequisites.length; each course enters the ready collection once and each edge is relaxed once, while the adjacency list and in-degree array hold O(V + E) entries.
Interview pitfalls
- Reversing edge direction: [a, b] means b before a, so the edge runs from b to a; the other way yields an invalid order.
- Returning a partial order when a cycle exists; the length check against numCourses is the cycle detector.
- In a DFS variant, a two-state visited flag cannot tell a back edge (cycle) from an edge to a finished node; keep a third in-progress state.
- Forgetting isolated courses with no prerequisites and no dependents; seeding from in-degree zero covers them, as example 3 shows.
Follow-up questions interviewers ask
- How would you return the lexicographically smallest valid order, and what does that cost?
- If new prerequisites arrive over time, how would you maintain a valid order incrementally?
Further reading on the technique: Topological sorting
Related LeetCode Problems
Practice more problems similar to Course Schedule II.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.