Dare2Solve
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.
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.
Graph Representation:
Topological Sorting:
Cycle Detection:
numCourses
, all courses can be finished and the order is valid.O(P)
time, where P
is the number of prerequisites.O(V + E)
time, where V
is the number of courses and E
is the number of prerequisites.O(V + P)
.O(V + E)
space.O(V)
space.O(V)
space.O(V + E)
.class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> order, inDegree(numCourses, 0);
unordered_map<int, vector<int>> map;
queue<int> 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<int>();
}
};
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 []
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] order = new int[numCourses];
int[] inDegree = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<Integer> 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];
}
}
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:[]
};