207. Course Schedule #190
Description
Problem Number
207
Problem Title
Course Schedule
LeetCode Link
https://leetcode.com/problems/course-schedule/description/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
1)Build an adjacency list. Graph[b] contains a if there is a prerequisite [a, b].
2)Create an array inDegree[a]++ for each [a, b].
3)Start a queue with all i such that inDegree[i]==0.
4)Remove one course u from the queue and increase the processed count. For each v in graph[u], reduce inDegree[v]. If inDegree[v] becomes 0 after decrementing, add v to the queue.
5)After the loop, if processed equals numCourses, return true; otherwise, return false.
Intuition
We have numCourses courses numbered from 0 to numCourses-1. The array prerequisites contains pairs [a, b], which means to take course a, you must finish course b first.
We can represent this as a directed graph: courses are nodes, and a prerequisite [a, b] is a directed edge from b to a, since b must come before a.
Instead of thinking about whether all courses can be completed, this transforms to: does this directed graph allow for a valid order to visit all nodes while respecting edges? In other words, is there a topological order for this graph?
If there is a cycle, like A → B → C → A, then you cannot complete the courses because each one depends on another in a loop. There is no starting node with an in-degree of 0.
We shall compute the in-degree, which is the number of incoming edges or prerequisites for every node. Then, you pick all nodes with an in-degree of zero, meaning these are the courses you can take right away. Remove them or mark them as done, and reduce the in-degree of their neighbors, which are the courses depending on them. Continue this until you either process all courses (good) or cannot make further progress while still having courses left (bad, indicating a cycle).
If we manage to process all numCourses courses using this method, we return true. If not, we return false.
The complexity is O(V + E), where V is the number of courses and E is the number of prerequisite pairs.
Key things to monitor include building the graph with the correct direction, ensuring the initial queue contains in-degree zero nodes, running the loop until the queue is empty, and keeping track of the number of processed courses.
Solution in C++
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto &p : prerequisites) {
int a = p[0], b = p[1];
graph[b].push_back(a);
inDegree[a]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) q.push(i);
}
int processed = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
processed++;
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
return processed == numCourses;
}
};