Difficulty: MediumGraphs

Course Schedule II

Problem in Plain English

Given a course count and prerequisite pairs, return any order in which all courses can be finished, or an empty array when a cycle makes it impossible.

Problem Statement

You are given numCourses courses labeled 0 to numCourses - 1 and prerequisites prerequisites[i] = [a, b] meaning course b comes before course a.

Return any ordering that respects every prerequisite, or an empty array when no such ordering exists.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a, b < numCourses
Each pair has distinct course labels a and b; all prerequisite pairs are unique.

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]

Course 0 has no prerequisites, so taking 0 then 1 respects the single dependency.

Example 2

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]

After 0, courses 1 and 2 are both ready; either may come first. Course 3 must follow both. Thus [0,2,1,3] and [0,1,2,3] are equally valid outputs.

Example 3

Input: numCourses = 1, prerequisites = []
Output: [0]

With no prerequisites the lone course stands alone in the order.

Example 4

Input: numCourses = 3, prerequisites = [[1,0],[0,1]]
Output: []

Courses 0 and 1 depend on each other. Course 2 is independently available, but finishing only it is insufficient: a full order is impossible, so return no order.

Intuition

A prerequisite is a directed constraint: [1,0] says 0 must precede 1. A valid order exists exactly when these constraints have no directed cycle. You can finish a course after exploring all of its prerequisites, or repeatedly take a course whose unfinished prerequisite count is zero. The first strategy uses DFS finish order; the second uses a queue of ready courses. Multiple ready courses can be chosen in any order.

Approaches

DFS Postorder

Solution Details

Reveal DFS Postorder: intuition, complexity, and code

Intuition

Follow a course to its prerequisites, then append it after every prerequisite has finished. Edges point from course to prerequisite in this DFS representation, so its finish order already puts prerequisites first and must not be reversed. An explicit frame stack remembers the next edge, while three states distinguish unseen, active, and finished courses.

Step-by-Step Logic

Build need[a] containing every b from [a,b], and initialize states 0=unseen, 1=active, 2=finished. Scan roots in course-label order; Example 1 gives need[0]=[] and need[1]=[0].
For an unseen root, mark it active and push a frame (course, next prerequisite index=0). The explicit stack implements DFS without relying on runtime recursion limits.
At the top frame, advance its edge index before descending into an unseen prerequisite. A finished prerequisite needs no action; an active prerequisite means a cycle, so return [].
When the frame has no edges left, pop it, mark it finished and append it. Example 1 finishes root 0 first, then root 1 sees 0 already finished and appends 1.
After every root is processed, return [0,1] for Example 1. In the cycle example, 0 leads to 1 then back to active 0, so return [] even if other courses are independent.

Why It Works

Each stack frame is an active course whose earlier prerequisite edges have been resolved. Unseen prerequisites receive their own frames; finished prerequisites are already in the order. An edge to an active course closes a directed cycle along the current stack, making a complete ordering impossible. Conversely, a directed cycle eventually leads to an active target when DFS reaches it. When a frame exhausts its edges, all its prerequisites are finished and already appear before it, so appending the course preserves every dependency. Starting DFS from every unseen course covers disconnected components and isolated courses. Each course finishes once, and no reversal is needed because edges point toward prerequisites.

Dry Run

DFS Postorder: variable states at each step
root / top frame	state [0,1]	next-edge index / action	stack after action	order
build	[0,0]	need=[[],[0]]	[]	[]
root 0	[1,0]	mark active; push (0,0)	[(0,0)]	[]
top 0	[2,0]	no edges; pop and finish	[]	[0]
root 1	[2,1]	mark active; push (1,0)	[(1,0)]	[0]
top 1	[2,1]	edge 0 to prerequisite 0; index 0 to 1; state[0]=2, skip	[(1,1)]	[0]
top 1	[2,2]	edges exhausted; pop and finish	[]	[0,1]
done	[2,2]	all roots processed; return	[]	[0,1]

Complexity Analysis

Time Complexity

O(V+E)

Space Complexity

O(V+E)

Let V = numCourses and E be the number of prerequisite pairs. Building adjacency takes O(V+E), every course is processed once, and every edge is examined once. Explicit frames hold at most V active courses, so chains of 2000 courses do not depend on runtime recursion limits. States, frame stack, answer list and Java result conversion use O(V). Adjacency stores O(V+E), which dominates auxiliary and returned storage. The input pairs are never modified. Both approaches have linear time; the optimal badge preserves the existing queue-based presentation.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int[] findOrder(int numCourses, int[][] prerequisites) {5        List<List<Integer>> need = new ArrayList<>();6        for (int i = 0; i < numCourses; i++) need.add(new ArrayList<>());7        for (int[] p : prerequisites) need.get(p[0]).add(p[1]);8        int[] state = new int[numCourses];9        List<Integer> order = new ArrayList<>();10        Deque<int[]> stack = new ArrayDeque<>();11        for (int root = 0; root < numCourses; root++) {12            if (state[root] != 0) continue;13            state[root] = 1;14            stack.push(new int[]{root, 0});15            while (!stack.isEmpty()) {16                int[] frame = stack.peek();17                int course = frame[0];18                if (frame[1] == need.get(course).size()) {19                    stack.pop();20                    state[course] = 2;21                    // Edges point to prerequisites: finish order is already forward.22                    order.add(course);23                    continue;24                }25                // Advance before descent so this edge is not repeated on return.26                int pre = need.get(course).get(frame[1]++);27                if (state[pre] == 1) return new int[0];28                if (state[pre] == 0) {29                    state[pre] = 1;30                    stack.push(new int[]{pre, 0});31                }32            }33        }34        int[] answer = new int[numCourses];35        for (int i = 0; i < numCourses; i++) answer[i] = order.get(i);36        return answer;37    }38}

Hints

Hint 1

Read each pair [a, b] as a directed edge from b to a, since b must come first.

Hint 2

Emit a course into the answer the moment all of its prerequisites are already emitted.

Hint 3

If emitted courses fall short of numCourses, a cycle blocks the rest, so return the empty array.

Edge Cases

No prerequisites means any order works, such as 0 through numCourses - 1 in sequence.
A single course with no prerequisites returns [0].
Outside the stated distinct-label constraint, a self-loop pair such as [0, 0] can never be scheduled and must return [].
A cycle in one disconnected component makes the whole schedule impossible even when other courses have no prerequisites.
A chain of 2000 courses checks traversal depth; the explicit DFS stack and queue run at default runtime settings.

Common Mistakes and Interview Tips

Returning a partial order when a cycle exists instead of the required empty array.
Using course-to-prerequisite edges in Kahn outgoing-dependents adjacency schedules prerequisites after their courses. Its graph must store b to a; DFS deliberately uses the opposite representation.
Accepting any single valid order as wrong during testing when many orders are acceptable.
Reversing DFS output despite its course-to-prerequisite adjacency. Reverse finish order is appropriate for the opposite edge orientation, not this code.
Using only one visited Boolean loses the distinction between an active cycle target and an already finished shared prerequisite.
Using JavaScript shift for the queue can add quadratic array movement; a head cursor keeps dequeue constant-time.
Recursive Python DFS can exceed the default stack limit on a long legal chain; these snippets use explicit frames.

Key Takeaway

When a problem asks for the order itself rather than just feasibility, emit nodes as their dependencies clear; Kahn construction turns cycle detection into ordering.