6.3 Course Schedule II

6.3.1 Problem Metadata

6.3.2 Description

Return a valid topological ordering of courses using prerequisites; return empty if a cycle prevents completion.

6.3.3 Examples

Example 1: Valid Topological Order

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: Course 0 is a prerequisite for courses 1 and 2; courses 1 and 2 are prerequisites for course 3

Example 2: Another Valid Order

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 0 must be completed before Course 1

Example 3: Cycle Exists

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Explanation: Impossible dependency cycle

6.3.4 Constraints

  • 1 ≤ numCourses ≤ 2000
  • 0 ≤ prerequisites.length ≤ 5000
  • Each prerequisite pair [a, b] satisfies 0 ≤ a, b < numCourses
  • All prerequisite pairs are unique

6.3.5 Solution - BFS Order

Use the same Kahn BFS as Course Schedule I, but record dequeue order as the topological order.

6.3.5.1 Walkthrough

  1. Build adjacency list and indegree counts.
  2. Enqueue all zero-indegree nodes.
  3. While queue not empty, pop course, append to order, and relax neighbors by decrementing indegree; enqueue neighbors that reach zero.
  4. If we placed all courses, return order; otherwise return empty array (cycle).

6.3.5.2 Analysis

  • Time Complexity: O(V + E)
  • Space Complexity: O(V + E)

6.3.5.3 Code - Java

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // Build graph: (prereq, course)
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    // Compute the indegree of all the vertices in the graph
    // For edge (course, prereq), indegree[course]++
    for (int[] edge : prerequisites) {
        int course = edge[0];
        int prereq = edge[1];
        graph.get(prereq).add(course);
        indegree[course]++;
    }

    Queue<Integer> queue = new LinkedList<>();

    // Initialize the queue with all vertices with no inbound edges
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    List<Integer> result = new ArrayList<>();

    while (!queue.isEmpty()) {
        int course = queue.poll();
        result.add(course);

        // Disconnect vertex from the graph
        // Decrease the indegree of the other end of the edge by 1
        for (int adj : graph.get(course)) {
            if (--indegree[adj] == 0) {
                queue.offer(adj);
            }
        }
    }

    // Check if the graph had a cycle/loop
    return result.size() == numCourses ? result.stream().mapToInt(i -> i).toArray() : new int[0];
}