grid47 Exploring patterns and algorithms
Oct 17, 2024
7 min read
Solution to LeetCode 210: Course Schedule II Problem
You are given a set of courses with prerequisites, and you need to find a valid order to take them, or return an empty array if no valid order exists.
Problem
Approach
Steps
Complexity
Input: You are given a number of courses, `numCourses`, and a list of prerequisite pairs where each pair [ai, bi] indicates that you need to take course bi before course ai.
Output: Return a valid order in which to complete all the courses, or an empty array if no valid order exists.
Example: For numCourses = 3 and prerequisites = [[1,0], [2,1]], the output is [0, 1, 2].
Constraints:
Goal: To determine if it is possible to complete all the courses by sorting the courses in a valid order considering their prerequisites.
Steps:
• Represent the courses and their prerequisites as a directed graph.
• Perform topological sorting on the graph using a queue to process nodes with no prerequisites.
• Return the topologically sorted order if all courses can be taken, otherwise return an empty array.
Goal: The constraints ensure the problem can be solved with an efficient algorithm for large inputs.
Steps:
• The number of courses can be up to 2000, so the solution should handle graphs with up to 2000 nodes and edges efficiently.
Assumptions:
• The input courses and prerequisites form a directed graph, which may or may not have cycles.
• Input: Example 1
• Explanation: In this case, you need to take course 1 after course 0, and course 2 after course 1, so the valid order is [0, 1, 2].
• Input: Example 2
• Explanation: The courses form a directed graph with dependencies, and a valid order is [0, 2, 1, 3].
• Input: Example 3
• Explanation: The prerequisites form a cycle, making it impossible to complete the courses, so the output is an empty array.
Approach: This problem can be solved using topological sorting on a directed graph representing course dependencies.
Observations:
• The problem involves checking if a directed graph is acyclic and finding a valid topological order.
• A queue can be used to process nodes with no incoming edges (prerequisites), and we can iteratively build the valid order.
Steps:
• Represent the courses and their prerequisites as a directed graph.
• Track the number of incoming edges (prerequisites) for each course.
• Use a queue to process courses that have no prerequisites (i.e., courses with zero incoming edges).
• For each processed course, reduce the incoming edges of its dependent courses and add those with no remaining prerequisites to the queue.
• If all courses are processed, return the topologically sorted order. Otherwise, return an empty array.
Empty Inputs:
• If no prerequisites are given, the courses can be completed in any order.
Large Inputs:
• The solution must handle up to 2000 courses efficiently.
Special Values:
• If the prerequisites form a cycle, it is impossible to complete the courses.
Constraints:
• Ensure that the solution works within the time limits for large arrays (O(n + m) time complexity).
vector<int> findOrder(int n, vector<vector<int>>& pre) {
vector<vector<int>> gph(n);
vector<int> incnt(n, 0);
for(int i =0; i < pre.size(); i++) {
gph[pre[i][1]].push_back(pre[i][0]);
incnt[pre[i][0]]++;
}
queue<int> q;
for(int i =0; i < n; i++)
if(incnt[i] ==0)
q.push(i);
vector<int> ans;
while(!q.empty()) {
int y = q.front();
ans.push_back(y);
q.pop();
for(autox: gph[y]) {
incnt[x]--;
if(incnt[x] ==0)
q.push(x);
}
}
return ans.size() == n?ans: vector<int>();
}
1 : Function Definition
vector<int> findOrder(int n, vector<vector<int>>& pre) {
Define the function `findOrder`, which takes an integer `n` (number of courses/nodes) and a 2D vector `pre` (prerequisites), and returns the topological order of nodes.
2 : Graph Initialization
vector<vector<int>> gph(n);
Initialize an adjacency list `gph` to represent the directed graph, where each node will store a list of its neighbors (nodes that depend on it).
3 : In-degree Initialization
vector<int> incnt(n, 0);
Initialize a vector `incnt` to keep track of the in-degree (number of incoming edges) for each node. Set all in-degrees initially to 0.
4 : Building Graph
for(int i =0; i < pre.size(); i++) {
Loop through the prerequisite pairs in `pre` to build the graph and update the in-degrees.
5 : Graph Population
gph[pre[i][1]].push_back(pre[i][0]);
For each pair in `pre`, add the directed edge from `pre[i][1]` to `pre[i][0]` in the adjacency list `gph`.
6 : In-degree Update
incnt[pre[i][0]]++;
Increase the in-degree of the node `pre[i][0]`, indicating that it has one more prerequisite.
7 : Queue Initialization
queue<int> q;
Initialize a queue `q` to keep track of nodes with no prerequisites (i.e., nodes with an in-degree of 0).
8 : Queue Population
for(int i =0; i < n; i++)
Loop through all nodes and add those with no incoming edges (in-degree of 0) to the queue.
9 : In-degree Check
if(incnt[i] ==0)
Check if the current node has no prerequisites (in-degree 0), indicating it can be processed.
10 : Queue Push
q.push(i);
Add the current node with no prerequisites to the queue.
11 : Answer Initialization
vector<int> ans;
Initialize an empty vector `ans` to store the topologically sorted nodes.
12 : Processing Queue
while(!q.empty()) {
While the queue is not empty, process each node in topological order.
13 : Node Processing
int y = q.front();
Get the front node from the queue to process.
14 : Answer Update
ans.push_back(y);
Add the current node `y` to the answer vector `ans` as part of the topological order.
15 : Queue Pop
q.pop();
Remove the processed node from the front of the queue.
16 : Graph Traversal
for(autox: gph[y]) {
For each node `x` that depends on the current node `y`, reduce its in-degree by 1.
17 : In-degree Decrement
incnt[x]--;
Decrement the in-degree of node `x`, as one of its prerequisites (`y`) has been processed.
18 : Queue Update
if(incnt[x] ==0)
If node `x` now has no prerequisites left (in-degree 0), it can be added to the queue.
19 : Queue Push Again
q.push(x);
Add node `x` to the queue for processing.
20 : Return Statement
return ans.size() == n?ans: vector<int>();
If all nodes have been processed (i.e., the answer size equals `n`), return the topologically sorted order; otherwise, return an empty vector indicating a cycle or an impossible ordering.
Best Case: O(n + m), where n is the number of courses and m is the number of prerequisites.
Average Case: O(n + m), since all nodes and edges must be processed.
Worst Case: O(n + m), in the worst case all courses and prerequisites must be processed.
Description: The time complexity is dominated by the graph traversal and topological sorting.
Best Case: O(n + m), since all the nodes and edges must be stored in memory.
Worst Case: O(n + m), to store the graph and incoming edges.
Description: The space complexity is proportional to the number of nodes (courses) and edges (prerequisites).
