You are given the number of courses and a list of prerequisite pairs.
Your task is to find an ordering in which you can finish all courses.
This is a classic directed graph problem where each course is a node, and each prerequisite is a directed edge.
If a valid ordering exists, return it.
If it is impossible due to cycles, return an empty array.
Understanding the Problem
Example:
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Meaning:
To take course 1, you must complete 0
To take course 2, you must complete 0
To take course 3, you must complete 1 and 2
One valid order is: [0, 1, 2, 3]
If there is a cycle (like 0 depends on 1 and 1 depends on 0), no valid ordering exists.
Approach (Explained in Simple Language)
The best solution uses Topological Sorting using Kahn’s Algorithm.
Here is the concept in very simple terms:
1. Represent courses as a directed graph
Each course is a node.
Each prerequisite pair [a, b] means b → a (b must come before a).
2. Count indegree of each node
Indegree means how many prerequisites a course has.
Example: indegree[a] = number of courses required before a.
3. Start with all courses that have indegree 0
These have no prerequisites and can be taken immediately.
Put all such courses into a queue.
4. Process the queue
Repeatedly remove a course from the queue and add it to the result ordering.
Then reduce the indegree of its dependent courses.
If reducing indegree makes some course reach 0, add it to the queue.
5. If all courses are processed, the ordering is valid
Otherwise, if there are unprocessed courses with indegree > 0, a cycle exists.
In that case, return an empty array.
Java Code
import java.util.*;
public class CourseScheduleII {
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[] pre : prerequisites) {
int course = pre[0];
int prereq = pre[1];
graph.get(prereq).add(course);
indegree[course]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int[] result = new int[numCourses];
int index = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
result[index++] = current;
for (int next : graph.get(current)) {
indegree[next]--;
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
if (index == numCourses) {
return result;
}
return new int[0];
}
public static void main(String[] args) {
CourseScheduleII solution = new CourseScheduleII();
int[][] prerequisites = {{1,0},{2,0},{3,1},{3,2}};
int[] result = solution.findOrder(4, prerequisites);
System.out.println(Arrays.toString(result));
}
}
Dry Run
Input:
numCourses = 4
prerequisites = [[1,0], [2,0], [3,1], [3,2]]
Meaning:
0 → 1
0 → 2
1 → 3
2 → 3
We want the order such that prerequisites appear first.
Step 1: Build graph and indegree array
Graph representation:
0 → [1, 2]
1 → [3]
2 → [3]
3 → []
Indegree:
0 = 0
1 = 1
2 = 1
3 = 2
Explanation:
1 depends on 0
2 depends on 0
3 depends on 1 and 2
Step 2: Add all courses with indegree 0 to queue
Queue = [0]
Only course 0 has no prerequisites.
Step 3: Process queue
Remove 0
Order = [0]
Reduce indegree of 1 and 2:
indegree[1] becomes 0
indegree[2] becomes 0
Add both to queue:
Queue = [1, 2]
Remove 1
Order = [0, 1]
Reduce indegree of 3:
indegree[3] becomes 1
Queue = [2]
Remove 2
Order = [0, 1, 2]
Reduce indegree of 3:
indegree[3] becomes 0
Add 3 to queue:
Queue = [3]
Remove 3
Order = [0, 1, 2, 3]
No further neighbors.
Step 4: Check if we processed all courses
index = 4 which is equal to numCourses = 4
So ordering is valid.
Output = [0, 1, 2, 3]
Why This Approach Works
Topological sorting is designed for problems where one task must come before another.
By repeatedly removing nodes with zero indegree, we ensure that all prerequisites of every course come before it in the final ordering.
If a cycle exists, no node will reach indegree 0, and we know no valid course ordering is possible.