grid47 Exploring patterns and algorithms
Oct 17, 2024
7 min read
Solution to LeetCode 207: Course Schedule Problem
You are given a set of courses and a list of prerequisites. Each prerequisite is a pair of courses where the second course must be taken before the first one. Determine if it is possible to complete all courses based on these prerequisites. If there are cycles in the dependencies, it would be impossible to finish all courses.
Problem
Approach
Steps
Complexity
Input: You are given an integer numCourses representing the total number of courses and an array prerequisites where each element [a, b] indicates that course b must be completed before course a.
Output: Return true if it is possible to finish all the courses. Otherwise, return false.
Example: Output: true
Constraints:
• The returned value must indicate whether it is possible to complete all courses given the prerequisites.
Goal: The goal is to determine if there is a cycle in the prerequisite graph. If there is no cycle, return true. If a cycle exists, return false.
Steps:
• Create a graph where each course points to its dependent courses.
• Use a counter to track the number of prerequisites for each course.
• Start with the courses that have no prerequisites and reduce the count of prerequisites for their dependent courses.
• If all courses can be completed (i.e., the prerequisite counter reaches zero for all), return true. Otherwise, return false if any course cannot be completed.
Goal: Ensure that the solution handles both small and large inputs efficiently.
Steps:
• The maximum number of courses is 2000.
• The maximum number of prerequisites is 5000.
• Courses are labeled with unique indices from 0 to numCourses - 1.
Assumptions:
• The input graph is well-formed with valid course numbers and prerequisites.
• Explanation: There are 2 courses. Course 1 requires course 0, and course 0 requires course 1. This forms a cycle, so it is impossible to complete all courses. The output is false.
Approach: The solution involves topological sorting of the graph formed by courses and their prerequisites. If there is a cycle in the graph, it is impossible to complete all courses.
Observations:
• The problem can be viewed as a cycle detection problem in a directed graph.
• Topological sorting using Kahn's algorithm can be used to detect cycles efficiently.
Steps:
• Construct a graph where each course points to its dependent courses.
• Count the prerequisites for each course and track courses with zero prerequisites.
• Process courses with zero prerequisites, reducing the count for dependent courses.
• If all courses can be processed, return true. If not, return false.
Empty Inputs:
• If there are no prerequisites, you can finish all courses.
Large Inputs:
• The solution should handle up to 2000 courses and 5000 prerequisites efficiently.
Special Values:
• If there is only one course, it can always be completed.
Constraints:
• Ensure that the solution handles cycles efficiently, especially with a large number of courses.
boolcanFinish(int n, vector<vector<int>>& pre) {
vector<vector<int>> graph(n);
vector<int> cnt(n, 0);
// Created graph and dependecy counter
for(int i =0; i < pre.size(); i++) {
graph[pre[i][1]].push_back(pre[i][0]);
cnt[pre[i][0]]++;
}
queue<int> q;
// Triaged course which does not have any dependency.
for(int i =0; i < n; i++)
if(cnt[i] ==0)
q.push(i);
while(!q.empty()) {
int size = q.size();
while(size-->0) {
int course = q.front();
q.pop();
for(intdep: graph[course]) {
cnt[dep]--;
if(cnt[dep] ==0) {
q.push(dep);
}
}
}
}
for(int i =0; i < n; i++)
if(cnt[i] !=0)
returnfalse;
returntrue;
}
1 : Function Definition
boolcanFinish(int n, vector<vector<int>>& pre) {
Define the function `canFinish` which takes the number of courses `n` and a vector of prerequisites `pre` representing course dependencies.
2 : Graph Initialization
vector<vector<int>> graph(n);
Initialize a graph where each course is represented by an index, and the corresponding vector stores its dependent courses.
3 : Dependency Counter Initialization
vector<int> cnt(n, 0);
Initialize a counter array `cnt` to track the number of prerequisites (dependencies) each course has.
4 : Graph and Dependency Counter Update
for(int i =0; i < pre.size(); i++) {
Iterate through each prerequisite pair in the `pre` list.
5 : Graph Update
graph[pre[i][1]].push_back(pre[i][0]);
For each prerequisite, add the dependent course to the corresponding graph entry.
6 : Dependency Counter Update
cnt[pre[i][0]]++;
Increment the counter for the dependent course, indicating it has one more prerequisite.
7 : Queue Declaration
queue<int> q;
Declare a queue `q` to hold the courses that are ready to be taken (i.e., those with zero dependencies).
8 : Queue Population
for(int i =0; i < n; i++)
Loop through all courses to find those with no prerequisites.
9 : Queue Population Condition
if(cnt[i] ==0)
Check if a course has no dependencies by examining its counter value.
10 : Enqueue Course
q.push(i);
Add the course with no dependencies to the queue.
11 : While Queue Not Empty
while(!q.empty()) {
Start a `while` loop to process courses in the queue until it's empty.
12 : Queue Size Calculation
int size = q.size();
Get the current number of courses in the queue, which need to be processed.
13 : Inner While Loop
while(size-->0) {
Iterate through all the courses in the queue.
14 : Dequeue Course
int course = q.front();
Get the course at the front of the queue to process.
15 : Pop Course from Queue
q.pop();
Remove the course from the queue after processing it.
16 : Process Dependencies
for(intdep: graph[course]) {
For each dependent course of the current course, reduce its dependency count.
17 : Dependency Counter Decrement
cnt[dep]--;
Decrement the counter for each dependent course, indicating one less prerequisite.
18 : Check If Course Is Ready
if(cnt[dep] ==0) {
If a course now has no dependencies, it can be added to the queue.
19 : Enqueue Ready Course
q.push(dep);
Enqueue the course that has no remaining prerequisites.
20 : Final Check Loop
for(int i =0; i < n; i++)
Loop through all courses to check for any remaining prerequisites.
21 : Cycle Detection
if(cnt[i] !=0)
If any course has remaining prerequisites, return `false` as there's a cycle.
22 : Return False
returnfalse;
Return `false` indicating it's not possible to finish all courses due to a cycle.
23 : Final Return
returntrue;
Return `true` if all courses can be finished without any cycles.
Best Case: O(n + e)
Average Case: O(n + e)
Worst Case: O(n + e)
Description: The time complexity is O(n + e), where n is the number of courses and e is the number of prerequisites.
Best Case: O(n + e)
Worst Case: O(n + e)
Description: The space complexity is O(n + e) due to the graph representation and the prerequisite count array.
