Given numCourses courses labeled from 0 to numCourses - 1 and a list of prerequisite pairs, return any valid order for completing all courses.
Each pair [course, prerequisite] means the prerequisite course must be completed before the course. Return an empty array when no valid order exists due to circular dependency.
Example 1
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: Course 0 appears before courses 1 and 2, and both appear before course 3.
Example 2
Input: numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]
Output: []
Explanation: The courses form a circular dependency, so no valid ordering exists.
Approach 1
Every course represents a vertex, while each prerequisite pair creates a directed edge from the prerequisite course to the dependent course. DFS appends a course only after all dependent paths have been explored, producing a postorder that becomes a valid course order after reversal.
A three-state array distinguishes unvisited, active, and finished courses. Reaching an active course indicates a circular dependency, making completion of all courses impossible.
Algorithm
Build an adjacency list containing an edge from every prerequisite to the corresponding dependent course.
Initialize a
statearray with0for unvisited courses and create an empty postorder list.Traverse every course and start DFS from each unvisited course, ensuring coverage of disconnected dependency chains.
Mark the current course with state
1, indicating membership in the active DFS path.Examine every dependent course; return an empty array upon reaching state
1, and continue DFS recursively upon reaching state0.Mark the current course with state
2after all dependent paths finish and append the course to the postorder list.Reverse the postorder list and return the result when no cycle is detected, placing every prerequisite before the corresponding dependent course.
Dry Run
course schedule II 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to build order after prerequisite paths finish. bool dfs(int course, vector<int>& state, vector<vector<int>>& adj, vector<int>& order) { // State 1 means course is active in current path. if (state[course] == 1) { return false; } // State 2 means course is already placed safely. if (state[course] == 2) { return true; } state[course] = 1; // Visit all courses depending on current course. for (int nextCourse : adj[course]) { if (!dfs(nextCourse, state, adj, order)) { return false; } } // Mark course finished and place in postorder. state[course] = 2; order.push_back(course); return true; }public: // Function to return a valid course order. vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); // Build edge from prerequisite to dependent course. for (auto& pairValue : prerequisites) { int course = pairValue[0]; int prerequisite = pairValue[1]; adj[prerequisite].push_back(course); } vector<int> state(numCourses, 0); vector<int> order; // Start DFS from every unvisited course. for (int course = 0; course < numCourses; course++) { if (state[course] == 0) { if (!dfs(course, state, adj, order)) { return {}; } } } // Reverse postorder to place prerequisites first. reverse(order.begin(), order.end()); return order; }};// Driver code.int main() { int numCourses = 4; vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}}; Solution sol; vector<int> ans = sol.findOrder(numCourses, prerequisites); // Print generated course order. for (int course : ans) { cout << course << " "; } return 0;}Complexity Analysis
Time Complexity: O(V+E), where V is the number of courses and E is the number of prerequisite relations; DFS processes every course and edge once.
Space Complexity: O(V+E), where the adjacency list stores V courses and E edges, while the state array, recursion stack, and answer require O(V) space.
Approach 2
Kahn’s Algorithm begins with all courses having indegree 0, since such courses have no pending prerequisites. Every removed course is appended directly to the resulting course order.
Processing a course reduces the indegree of all dependent courses. A dependent course enters the queue only after all prerequisites have been processed. An incomplete final order indicates a cycle.
Algorithm
Build an adjacency list and
indegreearray from all prerequisite pairs, storing the dependency graph and incoming-edge count of every course.Add every course having indegree
0to a queue, since such courses can be completed immediately.Initialize an empty order list to store courses in valid prerequisite order.
Continue processing while the queue contains courses, removing the front course and appending the course to the order.
Reduce the indegree of every dependent course, representing the completion of one required prerequisite.
Add a dependent course to the queue when the indegree becomes
0, indicating that all prerequisites have been completed.Return the order when the list contains
Vcourses; otherwise, return an empty array because a cycle prevents completion.
Note: Multiple valid course orders can exist. DFS and Kahn’s Algorithm may return different orders, but every order is correct when each prerequisite appears before the corresponding dependent course.
A cycle makes course completion impossible: DFS detects an active-path vertex, while Kahn’s Algorithm processes fewer than V courses. Both approaches return an empty array when a cycle exists.
Dry Run
course-schedule-ii-kahn-bfs-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to return a valid course order. vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); vector<int> indegree(numCourses, 0); // Build graph and indegree from prerequisites. for (auto& pairValue : prerequisites) { int course = pairValue[0]; int prerequisite = pairValue[1]; adj[prerequisite].push_back(course); indegree[course]++; } queue<int> q; // Add courses with no prerequisites. for (int course = 0; course < numCourses; course++) { if (indegree[course] == 0) { q.push(course); } } vector<int> order; // Process courses in prerequisite-safe order. while (!q.empty()) { int course = q.front(); q.pop(); order.push_back(course); // Remove current course as prerequisite for dependent courses. for (int nextCourse : adj[course]) { indegree[nextCourse]--; if (indegree[nextCourse] == 0) { q.push(nextCourse); } } } // Cycle exists when not all courses are processed. if (order.size() != numCourses) { return {}; } return order; }};// Driver code.int main() { int numCourses = 4; vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}}; Solution sol; vector<int> ans = sol.findOrder(numCourses, prerequisites); // Print generated course order. for (int course : ans) { cout << course << " "; } return 0;}Complexity Analysis
Time Complexity: O(V+E), where V is the number of courses and E is the number of prerequisite relations; every course and edge is processed once.
Space Complexity: O(V+E), where the adjacency list stores V courses and E edges, while the indegree array, queue, and answer require O(V) space.
Interview follow-up Questions
A valid course order must place every prerequisite before the dependent course, which matches topological ordering.
Be the first to add a comment.