🎨Now live: Try our Free AI Image Generation Feature

Description
Determine if it is possible to finish all courses given the number of courses and the prerequisites for each course. Each course is labeled from 0 to numCourses - 1
. You are given a list of prerequisite pairs, where prerequisites[i] = [ai, bi]
indicates that you must take course bi
before course ai
.
Intuition
The problem can be reduced to detecting if there is a cycle in a directed graph. If there is a cycle, it's impossible to complete all courses. We use topological sorting (Kahn's algorithm) to detect cycles and determine the order of courses.
Approach
- Graph Representation: - Use an adjacency matrix to represent the graph. - Use an array to keep track of the number of prerequisites each course has.
- Topological Sorting: - Initialize a queue to store courses with no prerequisites. - Use BFS to process each course, decrementing the prerequisite count 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. - 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 matrix takes
O(V^2)
space. - The requirements array takes
O(V)
space. - The queue takes up to
O(V)
space. - Total space complexity is
O(V^2)
.
Code
C++
class Solution {
public:
bool canFinish(int numCourses, vector>& prerequisites) {
if (numCourses <= 1 || prerequisites.empty()) {
return true;
}
vector> matrix(numCourses, vector(numCourses, 0));
vector requirements(numCourses, 0);
for (const auto& each : prerequisites) {
int course = each[0];
int pre = each[1];
if (matrix[pre][course] == 0) {
requirements[course]++;
}
matrix[pre][course] = 1;
}
queue stack;
for (int i = 0; i < numCourses; ++i) {
if (requirements[i] == 0) {
stack.push(i);
}
}
int counter = 0;
while (!stack.empty()) {
int course = stack.front();
stack.pop();
counter++;
for (int i = 0; i < numCourses; ++i) {
if (matrix[course][i] != 0) {
requirements[i]--;
if (requirements[i] == 0) {
stack.push(i);
}
}
}
}
return counter == numCourses;
}
};
Python
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if numCourses <= 1 or not prerequisites:
return True
matrix = [[0] * numCourses for _ in range(numCourses)]
requirements = [0] * numCourses
for course, pre in prerequisites:
if matrix[pre][course] == 0:
requirements[course] += 1
matrix[pre][course] = 1
stack = [i for i in range(numCourses) if requirements[i] == 0]
counter = 0
while stack:
course = stack.pop(0)
counter += 1
for i in range(numCourses):
if matrix[course][i] != 0:
requirements[i] -= 1
if requirements[i] == 0:
stack.append(i)
return counter == numCourses
Java
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 1 || prerequisites == null || prerequisites.length <= 1) {
return true;
}
int[][] matrix = new int[numCourses][numCourses];
int[] requirements = new int[numCourses];
for (int[] each : prerequisites) {
int course = each[0];
int pre = each[1];
if (matrix[pre][course] == 0) {
requirements[course]++;
}
matrix[pre][course] = 1;
}
java.util.Queue stack = new java.util.LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (requirements[i] == 0) {
stack.add(i);
}
}
int counter = 0;
while (!stack.isEmpty()) {
int course = stack.poll();
counter++;
for (int i = 0; i < numCourses; i++) {
if (matrix[course][i] != 0) {
requirements[i]--;
if (requirements[i] == 0) {
stack.add(i);
}
}
}
}
return counter == numCourses;
}
}
JavaScript
var canFinish = function (numCourses, prerequisites) {
if (numCourses <= 1 || !prerequisites || prerequisites.length <= 1) {
return true;
}
const matrix = Array.from({ length: numCourses }, () => new Array(numCourses).fill(0));
const requirements = new Array(numCourses).fill(0);
prerequisites.forEach(each => {
const [course, pre] = each;
if (matrix[pre][course] === 0) {
requirements[course]++;
}
matrix[pre][course] = 1;
});
const stack = [];
requirements.forEach((each, index) => {
if (each === 0) {
stack.push(index);
}
});
let counter = 0;
while (stack.length) {
const course = stack.shift();
counter++;
for (let i = 0; i < numCourses; i++) {
if (matrix[course][i] !== 0) {
requirements[i]--;
if (requirements[i] === 0) {
stack.push(i);
}
}
}
}
return counter === numCourses;
};