Course Schedule II
You have numCourses courses labeled 0 to numCourses - 1, and an array prerequisites where prerequisites[i] = [a, b] means course b must be taken before course a. Return an order in which you can take every course: an array that lists each course exactly once, with every prerequisite before the course that needs it. If several orders work, return any of them. If no valid order exists, return an empty array.
Examples
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] returns [0,1,2,3]
0 has no prerequisites, 1 and 2 each need only 0, and 3 needs both 1 and 2. [0,2,1,3] is also valid.
numCourses = 2, prerequisites = [[1,0],[0,1]] returns []
Each course requires the other, so neither can go first and no order exists.
numCourses = 3, prerequisites = [[1,0]] returns [0,2,1]
Course 2 appears in no pair but still has to be listed. Any order with 0 before 1 works, such as [0,1,2] or [2,0,1].
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
Hints
If you can finish them all, in what order should you list them out as you confirm each one?
Kahn's algorithm, emit each course as it leaves the queue.
Build adjacency lists and an indegree array. Push courses with indegree 0. Pop one, append to the output, and decrement indegrees of its neighbors, enqueuing those that hit 0. If the output has length numCourses, return it; otherwise return [].
Drill This: Your Approach First
Approach
Model each pair [a, b] as an edge b -> a and track each course's in-degree. Queue every course with in-degree 0. Each time you take a course off the queue, append it to the order and decrement the in-degree of the courses that depend on it, queuing any that drop to 0. A course only enters the queue after all its prerequisites are placed, so the order is valid. If fewer than numCourses courses get placed, the rest sit on a cycle, so return []. O(V + E) time and space.
Time
O(V + E)
Space
O(V + E)
Pitfall
Solutions
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[] indeg = new int[numCourses];
for (int[] e : prerequisites) {
graph.get(e[1]).add(e[0]);
indeg[e[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) queue.offer(i);
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int c = queue.poll();
order[idx++] = c;
for (int nb : graph.get(c)) {
if (--indeg[nb] == 0) queue.offer(nb);
}
}
return idx == numCourses ? order : new int[0];
}
}from collections import deque, defaultdict
class Solution:
def findOrder(self, numCourses: int, prerequisites):
graph = defaultdict(list)
indeg = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
queue = deque(i for i in range(numCourses) if indeg[i] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for nb in graph[c]:
indeg[nb] -= 1
if indeg[nb] == 0:
queue.append(nb)
return order if len(order) == numCourses else []