06-Course-Schedule-II.md

Course Schedule II

Problem Link

https://leetcode.com/problems/course-schedule-ii/

---

Pattern

• Topological Sort

---

Approach

Use indegree counts and return the topological order of courses if the graph is acyclic.

---

Time Complexity

O(V + E)

Space Complexity

O(V + E)

---

Java Solution

import java.util.*;
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[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];
    }
}