Course Schedule 🧠
LeetCode Link: Course Schedule
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 207 - Course Schedule
Description: 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. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.
Intuition: This problem can be approached as a graph problem where the courses represent nodes and the prerequisites represent directed edges. To determine if it is possible to finish all courses, we need to check if there is a cycle in the graph. If there is a cycle, it means there is a dependency loop, and we cannot finish all the courses.
Approach:
- Build an adjacency list representation of the graph using the prerequisites.
- Initialize a visited array to track the visited nodes during the DFS traversal.
- Iterate through each node in the graph and perform a DFS traversal to detect cycles:
- If the current node is being visited, it means there is a cycle, so return false.
- If the current node is not visited, perform a DFS traversal on its neighbors.
- If no cycles are detected after the DFS traversal, return true.
⌛ Time Complexity: The time complexity is O(V + E), where V is the number of courses (nodes) and E is the number of prerequisites (edges). We visit each course and prerequisite once.
💾 Space Complexity: The space complexity is O(V + E), where V is the number of courses (nodes) and E is the number of prerequisites (edges). This is the space used for the adjacency list and the visited array.
Solutions 💡
Cpp 💻
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses); // Adjacency list representation of the graph
vector<int> visited(numCourses, 0); // Visited array to track the visited nodes
// Build the graph
for (const auto &prerequisite : prerequisites) {
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph[course].push_back(prerequisiteCourse);
}
// Perform a DFS traversal to detect cycles
for (int course = 0; course < numCourses; ++course) {
if (!dfs(course, graph, visited)) {
return false;
}
}
return true;
}
private:
bool dfs(int course, vector<vector<int>> &graph, vector<int> &visited) {
// If the current course is being visited, it means there is a cycle
if (visited[course] == 1) {
return false;
}
// If the current course is already visited, return true
if (visited[course] == -1) {
return true;
}
visited[course] = 1; // Mark the current course as being visited
// Perform a DFS traversal on the neighbors
for (const auto &neighbor : graph[course]) {
if (!dfs(neighbor, graph, visited)) {
return false;
}
}
visited[course] = -1; // Mark the current course as visited
return true;
}
};
// Topological sort
// Same time and space complexity but this can be more efficient in terms of practical performance
/*
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses); // Adjacency list representation of the graph
vector<int> inDegree(numCourses, 0); // In-degree of each course
// Build the graph and calculate the in-degree of each course
for (const auto& prerequisite : prerequisites) {
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph[prerequisiteCourse].push_back(course);
++inDegree[course];
}
queue<int> q; // Queue to store courses with in-degree 0
// Enqueue courses with in-degree 0
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// Perform topological sorting
while (!q.empty()) {
int course = q.front();
q.pop();
--numCourses; // Decrement the number of remaining courses
// Decrement the in-degree of neighbors and enqueue if their in-degree becomes 0
for (const auto& neighbor : graph[course]) {
if (--inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return numCourses == 0;
}
};
*/
Python 🐍
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = {i: [] for i in range(numCourses)}
in_degree = [0] * numCourses
# Construct the graph and count in-degrees
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# Initialize a queue with nodes having in-degree zero
queue = collections.deque(
[course for course, degree in enumerate(in_degree) if degree == 0]
)
# Perform topological sorting and update in-degrees
while queue:
node = queue.popleft()
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If any course has in-degree greater than zero, there's a cycle
return all(degree == 0 for degree in in_degree)