Course Schedule II

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.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

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

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

Approach: Topological Sort (Kahn’s Algorithm)

Algorithm

1. Build an adjacency list where prerequisites[i] = [ai, bi] means edge bi -> ai (bi must be taken before ai)
2. Track the indegree of every course
3. BFS from all courses with indegree 0: pop a course, append it to the order, decrement the indegree of its successors, and enqueue any that reach 0
4. If the order has fewer than numCourses courses, a cycle exists -> return an empty array

Time & Space Complexity

• Time Complexity: O(V + E) - V courses and E prerequisites are each processed once
• Space Complexity: O(V + E) - the adjacency list and the queue

Java Implementation

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class CourseScheduleII {

    /**
     * Return a valid order to finish all courses, or an empty array if impossible.
     * @param numCourses Number of courses
     * @param prerequisites Pairs [ai, bi] meaning bi must precede ai
     * @return Course order or an empty array
     */
    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[] pre : prerequisites) {
            int a = pre[0];
            int b = pre[1];
            graph.get(b).add(a);
            indegree[a]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        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)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return index == numCourses ? order : new int[0];
    }

    // Test method
    public static void main(String[] args) {
        CourseScheduleII cs = new CourseScheduleII();
        System.out.println("Input: numCourses = 2, prerequisites = [[1,0]]");
        System.out.println("Output: " + java.util.Arrays.toString(cs.findOrder(2, new int[][]{{1, 0}})));
        // Expected: [0, 1]

        System.out.println("Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]");
        System.out.println("Output: " + java.util.Arrays.toString(cs.findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
        // Expected: one valid order, e.g. [0, 1, 2, 3]
    }
}

Example Walkthrough

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

1. Edges: 0->1, 0->2, 1->3, 2->3. Indegrees: 0:0, 1:1, 2:1, 3:2
2. Start with course 0 -> order [0]; decrement 1 and 2 to indegree 0
3. Pop 1 (or 2): order [0,1]; decrement 3
4. Pop 2: order [0,1,2]; decrement 3 to 0
5. Pop 3: order [0,1,2,3]

A cycle (e.g. [[0,1],[1,0]]) leaves one course with indegree 1, so the order length is less than numCourses and an empty array is returned.

Key Points

1. Edge Direction: [ai, bi] becomes the edge bi -> ai because the prerequisite must come first
2. Indegree: A course is ready only when all its prerequisites are processed
3. Cycle Detection: Processing fewer than numCourses courses means a cycle exists
4. Any Valid Order: Multiple topological orders exist; any one is accepted
5. Disconnected Courses: Courses with no prerequisites start with indegree 0 and are processed immediately