Course Schedule II
Problem link: https://leetcode.com/problems/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.
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.
Input
An integer numCourses (V) and a 2D array prerequisites (E).
Output
An array representing the course sequence, or [] if impossible.
Example
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]
Explanation
Course 0 has no prerequisites. Once 0 is done, 1 and 2 become available. Once both are done, 3 can be taken.
Brute Force
Intuition
Check every possible permutation of the courses to see if any satisfy the prerequisite rules.
Approach
- Generate all V! possible orderings of the courses.
- For each ordering, iterate through the list of E prerequisites.
- For a prerequisite [a, b], find the indices of a and b in the current ordering.
- If index(b) < index(a) for all prerequisites, the ordering is valid.
Code (Java)
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] courses = new int[numCourses];
for(int i = 0; i < numCourses; i++) courses[i] = i;
List<int[]> result = new ArrayList<>();
// Standard backtracking permutation logic
generatePermutations(courses, 0, prerequisites, result);
return result.isEmpty() ? new int[0] : result.get(0);
}
private boolean isValid(int[] order, int[][] prerequisites) {
Map<Integer, Integer> pos = new HashMap<>();
for(int i = 0; i < order.length; i++) pos.put(order[i], i);
for(int[] pre : prerequisites) {
// course pre[1] must come before pre[0]
if(pos.get(pre[1]) > pos.get(pre[0])) return false;
}
return true;
}
Complexity Analysis
There are V! permutations. For each, we spend O(V) to map positions and O(E) to validate prerequisites. This grows factorially, making it unusable for V > 10.
Optimal Solution
Intuition
Treat courses as nodes in a graph. Use Kahn's Algorithm (BFS) to pick courses with zero prerequisites, then update their dependencies.
Approach
- Create an adjacency list representing the graph.
- Create an
indegreearray whereindegree[i]is the number of prerequisites for coursei. - Add all courses with
indegree == 0to a Queue. - While the Queue is not empty:
- Poll course
u, add it to the final result array. - For every neighbor
vofu, decrementindegree[v]. - If
indegree[v]becomes 0, addvto the Queue.
- Poll course
- If the result array contains fewer than
numCourses, a cycle exists.
Code (Java)
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] adj = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
for (int[] pre : prerequisites) {
adj[pre[1]].add(pre[0]);
indegree[pre[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) q.add(i);
}
int[] res = new int[numCourses];
int count = 0;
while (!q.isEmpty()) {
int curr = q.poll();
res[count++] = curr;
for (int next : adj[curr]) {
if (--indegree[next] == 0) q.add(next);
}
}
return count == numCourses ? res : new int[0];
}
}
Complexity Analysis
Time: We visit each vertex once and each edge once during graph construction and BFS. Space: The adjacency list stores all E edges, and the indegree array/Queue store up to V vertices.
Quick Revision (Brute Force)
- Generate all permutations: O(V!)
- Validate each against E constraints
- Total: O(V! * (V+E))
Quick Revision (Optimal)
- Kahn's Algorithm (BFS): O(V + E)
- Space: O(V + E) for adjacency list
- Cycle detection included (count != V)