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.
[0, 1], indicates that to take course 0 you have to first take course 1.Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = [] Output: [0]
Constraints:
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi[ai, bi] are distinct.The #210 Course Schedule II problem asks you to return a valid order of courses given prerequisite pairs. This is a classic topological sorting problem on a directed graph where courses are nodes and prerequisites form edges.
A common strategy is to build an adjacency list and track the in-degree of each course. Using BFS (Kahn’s Algorithm), you start with courses that have zero prerequisites, process them, and gradually reduce the in-degree of dependent courses. If all courses are processed, the resulting sequence is a valid order.
Another approach uses DFS with cycle detection. During traversal, nodes are marked with states (unvisited, visiting, visited). If a cycle is detected, it means the schedule is impossible. Otherwise, nodes are added to the order after exploring their dependencies.
Both approaches efficiently detect cycles and generate a valid course ordering. The overall complexity is O(V + E), where V is the number of courses and E is the number of prerequisite relationships.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS (Kahn's Algorithm / In-degree) | O(V + E) | O(V + E) |
| DFS with Cycle Detection | O(V + E) | O(V + E) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
<a href="https://www.youtube.com/watch?v=ozso3xxkVGU" target="_blank">Topological Sort via DFS</a> - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via <a href="http://en.wikipedia.org/wiki/Topological_sorting#Algorithms" target="_blank">BFS</a>.
Consider courses as nodes in a directed graph, and prerequisites as directed edges. We can apply Kahn's algorithm for topological sorting to find the order of courses to take. The algorithm works by using an in-degree array that tracks the number of prerequisites for each course. Courses with zero in-degrees can be taken immediately. As our course order is populated, we decrement the in-degree of their dependent courses, allowing them to be taken in subsequent steps.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph and the in-degree array.
1function findOrder(numCourses, prerequisites) {
2 let inDegree = new Array(numCourses).fill(0);
3 let graph = Array.from({length: numCourses}, () => []);
4
5 for (let [course, prereq] of prerequisites) {
6 graph[prereq].push(course);
7 inDegree[course]++;
8 }
9
10 let queue = [];
11 for (let i = 0; i < numCourses; i++) {
12 if (inDegree[i] === 0) queue.push(i);
13 }
14
15 let order = [];
16 while (queue.length) {
17 const node = queue.shift();
18 order.push(node);
19 for (let neighbor of graph[node]) {
20 inDegree[neighbor]--;
21 if (inDegree[neighbor] === 0) queue.push(neighbor);
22 }
23 }
24
25 return order.length === numCourses ? order : [];
26}
27The code above follows the same logic as the Python solution. It constructs the prerequisite graph and maintains an in-degree array before performing BFS with a queue to determine a valid course order.
Similar to the Kahn's algorithm approach, but using a depth-first search (DFS) to detect cycles and determine the order of courses. In this method, courses are visited, and if a course is revisited while still in the recursion stack, it indicates a cycle, making course completion impossible. The order is determined by recording the exit point of each node during the DFS.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph structure and visited array.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] FindOrder(int numCourses, int[][] prerequisites) {
List<int>[] graph = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new List<int>();
foreach (var prereq in prerequisites) graph[prereq[1]].Add(prereq[0]);
bool[] visited = new bool[numCourses];
bool[] recStack = new bool[numCourses];
List<int> order = new List<int>();
for (int i = 0; i < numCourses; i++) {
if (HasCycle(graph, visited, recStack, i, order))
return new int[0];
}
order.Reverse();
return order.ToArray();
}
private bool HasCycle(List<int>[] graph, bool[] visited,
bool[] recStack, int node, List<int> order) {
if (recStack[node]) return true;
if (visited[node]) return false;
visited[node] = true;
recStack[node] = true;
foreach (int neighbor in graph[node])
if (HasCycle(graph, visited, recStack, neighbor, order))
return true;
recStack[node] = false;
order.Add(node);
return false;
}
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Course Schedule II and similar graph problems frequently appear in FAANG and other top tech company interviews. They test understanding of graphs, cycle detection, and topological sorting—core concepts in algorithmic problem solving.
An adjacency list is typically used to represent the graph of course dependencies. Along with this, an in-degree array or visitation state array helps track prerequisites and detect cycles during BFS or DFS traversal.
The optimal approach is to perform a topological sort on the course dependency graph. This can be done using BFS with Kahn’s Algorithm or DFS with cycle detection. Both methods efficiently detect cycles and generate a valid ordering in O(V + E) time.
Topological sorting is used because the problem involves ordering tasks with dependency constraints. In a directed acyclic graph, topological order ensures every course appears after its prerequisites, making it ideal for scheduling problems.
The C# solution leverages DFS to topologically sort the courses while simultaneously checking for cycles. The recursion stack helps identify cycles, while completed nodes are added to a list in post-order to establish the course sequence.