Approach

Course Schedule II

Problem Statement

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.

Examples

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] or [0,1,2,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]

Approach: Topological Sort with DFS

This is a topological sort problem - finding a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.

Algorithm Steps:

Build Graph: Create adjacency list from prerequisites
DFS with Cycle Detection:
- Track visited (fully processed nodes)
- Track visiting (nodes in current DFS path)
- If we encounter a visiting node, we found a cycle → impossible
Topological Ordering:
- After exploring all neighbors, add node to order
- Reverse the order at the end (post-order DFS)

Why This Works:

Cycle Detection: Three states (unvisited, visiting, visited) detect cycles
Post-order DFS: Adding nodes after exploring neighbors ensures dependencies come first
Reverse Order: Post-order DFS gives reverse topological sort, so we reverse it

Time Complexity: O(V + E)

V = number of courses (vertices)
E = number of prerequisites (edges)
Visit each node and edge once

Space Complexity: O(V + E)

Adjacency list: O(E)
Recursion stack: O(V)
Visited sets: O(V)

Key Points

Topological sort only exists for Directed Acyclic Graphs (DAGs)
If there's a cycle, it's impossible to complete all courses
DFS post-order naturally gives topological ordering (reversed)
Can also be solved with BFS (Kahn's algorithm)

Solution

java

1class Solution {
2    private List<Integer> order;
3    private boolean hasCycle;
4
5    public int[] findOrder(int numCourses, int[][] prerequisites) {
6        // Build adjacency list
7        List<List<Integer>> graph = new ArrayList<>();
8        for (int i = 0; i < numCourses; i++) {
9            graph.add(new ArrayList<>());
10        }
11        for (int[] prereq : prerequisites) {
12            int course = prereq[0];
13            int prerequisite = prereq[1];
14            graph.get(prerequisite).add(course);
15        }
16
17        // Track visited and visiting nodes
18        boolean[] visited = new boolean[numCourses];
19        boolean[] visiting = new boolean[numCourses];
20        order = new ArrayList<>();
21        hasCycle = false;
22
23        // Try DFS from each unvisited node
24        for (int i = 0; i < numCourses; i++) {
25            if (!visited[i]) {
26                dfs(i, graph, visited, visiting);
27                if (hasCycle) {
28                    return new int[0]; // Cycle detected, impossible
29                }
30            }
31        }
32
33        // Reverse the order for topological sort
34        Collections.reverse(order);
35        return order.stream().mapToInt(i -> i).toArray();
36    }
37
38    private void dfs(int course, List<List<Integer>> graph,
39                     boolean[] visited, boolean[] visiting) {
40        if (hasCycle) return;
41
42        visiting[course] = true;
43
44        for (int next : graph.get(course)) {
45            if (visiting[next]) {
46                // Cycle detected
47                hasCycle = true;
48                return;
49            }
50            if (!visited[next]) {
51                dfs(next, graph, visited, visiting);
52            }
53        }
54
55        visiting[course] = false;
56        visited[course] = true;
57        order.add(course); // Post-order: add after exploring neighbors
58    }
59}
60
61/**
62 * Alternative solution using BFS (Kahn's algorithm)
63 */
64class SolutionBFS {
65    public int[] findOrder(int numCourses, int[][] prerequisites) {
66        // Build graph and calculate in-degrees
67        List<List<Integer>> graph = new ArrayList<>();
68        int[] inDegree = new int[numCourses];
69
70        for (int i = 0; i < numCourses; i++) {
71            graph.add(new ArrayList<>());
72        }
73
74        for (int[] prereq : prerequisites) {
75            int course = prereq[0];
76            int prerequisite = prereq[1];
77            graph.get(prerequisite).add(course);
78            inDegree[course]++;
79        }
80
81        // Queue for courses with no prerequisites
82        Queue<Integer> queue = new LinkedList<>();
83        for (int i = 0; i < numCourses; i++) {
84            if (inDegree[i] == 0) {
85                queue.offer(i);
86            }
87        }
88
89        int[] order = new int[numCourses];
90        int index = 0;
91
92        // Process courses level by level
93        while (!queue.isEmpty()) {
94            int course = queue.poll();
95            order[index++] = course;
96
97            for (int next : graph.get(course)) {
98                inDegree[next]--;
99                if (inDegree[next] == 0) {
100                    queue.offer(next);
101                }
102            }
103        }
104
105        // Check if all courses were processed
106        if (index != numCourses) {
107            return new int[0]; // Cycle exists
108        }
109
110        return order;
111    }
112}
113
114/**
115 * Solution with detailed tracking
116 */
117class SolutionDetailed {
118    private enum State { UNVISITED, VISITING, VISITED }
119
120    public int[] findOrder(int numCourses, int[][] prerequisites) {
121        // Build adjacency list
122        Map<Integer, List<Integer>> graph = new HashMap<>();
123        for (int i = 0; i < numCourses; i++) {
124            graph.put(i, new ArrayList<>());
125        }
126        for (int[] prereq : prerequisites) {
127            graph.get(prereq[1]).add(prereq[0]);
128        }
129
130        State[] states = new State[numCourses];
131        Arrays.fill(states, State.UNVISITED);
132
133        List<Integer> order = new ArrayList<>();
134
135        for (int i = 0; i < numCourses; i++) {
136            if (states[i] == State.UNVISITED) {
137                if (!dfs(i, graph, states, order)) {
138                    return new int[0];
139                }
140            }
141        }
142
143        Collections.reverse(order);
144        return order.stream().mapToInt(i -> i).toArray();
145    }
146
147    private boolean dfs(int course, Map<Integer, List<Integer>> graph,
148                       State[] states, List<Integer> order) {
149        states[course] = State.VISITING;
150
151        for (int next : graph.get(course)) {
152            if (states[next] == State.VISITING) {
153                return false; // Cycle detected
154            }
155            if (states[next] == State.UNVISITED) {
156                if (!dfs(next, graph, states, order)) {
157                    return false;
158                }
159            }
160        }
161
162        states[course] = State.VISITED;
163        order.add(course);
164        return true;
165    }
166}
167