Course Schedule II

Link : Course Schedule II – LeetCode

1. Problem Statement

You are given:

• An integer numCourses (number of total courses, labeled from 0 to numCourses - 1)

• An array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai

Return:

• A valid ordering of courses you should take to finish all courses

• If there is no way to finish all courses (i.e., cycle exists), return an empty array

2. Examples

Example 1:

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

Example 2:

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

3. Constraints

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= numCourses * (numCourses - 1)

• prerequisites[i].length == 2

• All prerequisite pairs are valid course numbers

4. Intuition

This problem is a classical application of Topological Sorting of a Directed Acyclic Graph (DAG).

• Each course is a node

• Each prerequisite [a, b] is a directed edge from b to a (you must take b before a)

Why topological sorting?

We need to order courses such that prerequisites are completed before dependent courses.
Topological order guarantees that if there's an edge from u → v, then u appears before v in the ordering.

5. Why It Only Works on DAGs

Topological Sort only works on DAGs (Directed Acyclic Graphs) because:

• If there is a cycle, there is no valid ordering

• You’ll always be “waiting” on a course that is itself waiting on another

Example of a cycle:

[0 → 1], [1 → 2], [2 → 0]

No course can start without the previous being completed – this is impossible.

6. Approach 1: Kahn's Algorithm (BFS Topological Sort)

Algorithm:

1. Build the adjacency list

2. Compute in-degree of each node

3. Push all nodes with in-degree 0 to a queue

4. While the queue is not empty:

   • Pop node and add to result

   • Decrease in-degree of its neighbors

   • If neighbor’s in-degree becomes 0, push it to the queue

5. If result size equals numCourses → valid ordering
   Else → cycle exists → return []

7. Java Code: BFS (Kahn's Algorithm)

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for(int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }

        int[] indegree = new int[numCourses];
        for(int[] pre : prerequisites) {
            int u = pre[1], v = pre[0];
            adj.get(u).add(v);
            indegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        int[] result = new int[numCourses];
        int idx = 0;

        while(!q.isEmpty()) {
            int u = q.poll();
            result[idx++] = u;
            for(int v : adj.get(u)) {
                indegree[v]--;
                if(indegree[v] == 0) q.offer(v);
            }
        }

        return idx == numCourses ? result : new int[0];
    }
}

8. Dry Run Example

Input:

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

Adjacency List:

0 → [1, 2]
1 → [3]
2 → [3]

In-degree:

0 → 0
1 → 1
2 → 1
3 → 2

Steps:

• Queue = [0]

• Pop 0 → result = [0]

  • Decrease in-degree of 1 → 0 → Queue = [1]

  • Decrease in-degree of 2 → 0 → Queue = [1, 2]

• Pop 1 → result = [0, 1]

  • Decrease in-degree of 3 → 1

• Pop 2 → result = [0, 1, 2]

  • Decrease in-degree of 3 → 0 → Queue = [3]

• Pop 3 → result = [0, 1, 2, 3]

Final result = [0,1,2,3] (or [0,2,1,3] — both valid)

9. Time and Space Complexity

10. Optional: DFS-Based Topological Sort

If needed, the DFS-based approach can be implemented using:

• A visited array

• A recursion stack

• A post-order list (stack or list used in reverse)