Course Schedule II — Practice

Problem

Given numCourses and a list of prerequisite pairs [a, b] meaning you must take b before a, return an ordering of all courses that satisfies every prerequisite. Return an empty array if no valid ordering exists.

Examples

Example 1

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

Output: [0,1,2,3] (or [0,2,1,3])

Explanation: Course 0 has no prerequisites; 1 and 2 depend on 0; 3 depends on both 1 and 2.

Constraints

•1 <= numCourses <= 2000
•0 <= prerequisites.length <= 5000

Hints

Hint 1

This is Course Schedule (does a valid order exist) plus one requirement: return the order itself, not just yes/no.

Hint 2

Kahn's algorithm (BFS-based topological sort) naturally produces the order as a side effect of the process — track it as you go.

Hint 3

The same 'is there a cycle' detection from Course Schedule falls out for free here: if you can't place all N courses, a cycle exists.

Solutions

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]); // p[1] -> p[0]
        inDegree[p[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);

    int[] order = new int[numCourses];
    int index = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[index++] = course;
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return index == numCourses ? order : new int[0]; // fewer than numCourses placed means a cycle exists
}

Time: O(V + E) · Space: O(V + E)