🎨Now live: Try our Free AI Image Generation Feature

Description
Given the number of courses and a list of prerequisite pairs, determine the order in which courses should be taken to complete all courses. If it's impossible to complete all courses, return an empty array.
Intuition
This problem can be solved by performing topological sorting on a directed graph. The goal is to return a valid topological order of courses if one exists. If a cycle is detected, it means that it's impossible to complete all courses.
Approach
- Graph Representation: - Use an adjacency list to represent the graph. - Use an array to keep track of the in-degree (number of incoming edges) for each course.
- Topological Sorting: - Initialize a queue to store courses with no prerequisites (in-degree of zero). - Use BFS to process each course, decrementing the in-degree of connected courses. - Add courses with no remaining prerequisites to the queue.
- Cycle Detection:
- If the number of processed courses equals
numCourses
, all courses can be finished and the order is valid. - If not, there is a cycle in the graph, making it impossible to finish all courses.
Complexity
Time Complexity:
- Constructing the graph takes
O(P)
time, whereP
is the number of prerequisites. - Topological sorting takes
O(V + E)
time, whereV
is the number of courses andE
is the number of prerequisites. - Total time complexity is
O(V + P)
.
Space Complexity:
- The adjacency list takes
O(V + E)
space. - The in-degree array takes
O(V)
space. - The queue takes up to
O(V)
space. - Total space complexity is
O(V + E)
.
Code
C++
class Solution {
public:
vector findOrder(int numCourses, vector>& prerequisites) {
vector order, inDegree(numCourses, 0);
unordered_map> map;
queue queue;
for (auto& pre : prerequisites) {
int target = pre[0], preCourse = pre[1];
map[preCourse].push_back(target);
inDegree[target] += 1;
}
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
queue.push(i);
}
}
while (!queue.empty()) {
int node = queue.front();
queue.pop();
order.push_back(node);
if (map.find(node) != map.end()) {
for (int target : map[node]) {
inDegree[target] -= 1;
if (inDegree[target] == 0) {
queue.push(target);
}
}
}
}
return order.size() == numCourses ? order : vector();
}
};
Python
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
order = []
inDegree = [0] * numCourses
graph = {i: [] for i in range(numCourses)}
# Initialize the graph
for target, pre in prerequisites:
graph[pre].append(target)
inDegree[target] += 1
# Find all courses with no prerequisites
queue = [i for i in range(numCourses) if inDegree[i] == 0]
# Process each course
while queue:
node = queue.pop(0)
order.append(node)
for neighbor in graph[node]:
inDegree[neighbor] -= 1
if inDegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []
Java
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] order = new int[numCourses];
int[] inDegree = new int[numCourses];
Map> map = new HashMap<>();
Queue queue = new LinkedList<>();
// Initialize the graph
for (int[] pre : prerequisites) {
int target = pre[0], preCourse = pre[1];
map.computeIfAbsent(preCourse, k -> new ArrayList<>()).add(target);
inDegree[target] += 1;
}
// Find all courses with no prerequisites
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int index = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
order[index++] = node;
if (map.containsKey(node)) {
for (int target : map.get(node)) {
inDegree[target] -= 1;
if (inDegree[target] == 0) {
queue.offer(target);
}
}
}
}
return index == numCourses ? order : new int[0];
}
}
JavaScript
var findOrder = function (numCourses, prerequisites) {
const order = [], queue = []
const inDegree = new Array(numCourses).fill(0)
const map = new Map()
for (let [target, pre] of prerequisites) {
map.has(pre) ? map.get(pre).push(target) : map.set(pre, [target])
inDegree[target] += 1
}
console.log(map)
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.push(i)
}
}
while (queue.length != 0) {
let node = queue.shift()
order.push(node)
console.log(node, map.get(node))
if (map.has(node)) {
for (let tar of map.get(node)) {
inDegree[tar] -= 1
if (inDegree[tar] == 0) {
queue.push(tar)
}
}
}
}
return order.length==numCourses?order:[]
};