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.Problem Overview: You are given numCourses and prerequisite pairs where [a, b] means you must take course b before a. The task is to return a valid order to finish all courses. If a cycle exists in the dependency graph, no valid ordering exists.
Approach 1: Topological Sort using Kahn's Algorithm (BFS) (Time: O(V+E), Space: O(V+E))
This approach models the courses as a directed graph and performs a topological sort using BFS. Build an adjacency list and track the in-degree of each course. Push all nodes with in-degree 0 into a queue since they have no prerequisites. Repeatedly pop from the queue, add the course to the result order, and reduce the in-degree of its neighbors. When a neighbor's in-degree becomes 0, push it into the queue. If the final order contains all courses, the schedule is valid; otherwise a cycle exists. This approach is widely used in scheduling systems and is the most intuitive solution for dependency resolution problems.
Approach 2: DFS with Cycle Detection (Time: O(V+E), Space: O(V+E))
The DFS approach performs a depth-first traversal of the graph while tracking node states to detect cycles. Each course is marked as unvisited, visiting, or visited. When DFS explores a node already marked visiting, a cycle exists and the schedule is impossible. After exploring all neighbors of a node, add it to the ordering stack. The final topological order is obtained by reversing the stack. This technique relies on recursion and is a classic graph traversal pattern.
Both approaches rely on concepts from graph algorithms and topological sort. The BFS approach uses queue processing similar to Breadth-First Search, while the second uses recursion from Depth-First Search.
Recommended for interviews: Kahn's Algorithm is usually the expected solution because it directly models dependency resolution and avoids recursion edge cases. DFS with cycle detection demonstrates deeper graph knowledge and is often discussed as an alternative. Showing both proves you understand topological sorting from multiple perspectives.
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.
This solution uses a breadth-first search (BFS) starting from courses with zero prerequisites. As courses are completed, they are removed from their neighbors' prerequisites, enabling further courses to be completed in order. This ensures the result represents a valid topological sort of the course schedule.
JavaScript
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.
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.
The Java solution implements DFS to perform topological sorting while checking for cycles in the graph. During the recursive traversal, we maintain a recursion stack to detect back-edges, alerting us to any cycles in the graph.
C#
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.
| Approach | Complexity |
|---|---|
| Topological Sort using Kahn's Algorithm | Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites. |
| DFS with Cycle Detection | Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Topological Sort (Kahn's Algorithm - BFS) | O(V+E) | O(V+E) | Best for dependency resolution problems and iterative solutions without recursion |
| DFS with Cycle Detection | O(V+E) | O(V+E) | Useful when recursion is preferred or when detecting cycles during traversal |
Course Schedule - Graph Adjacency List - Leetcode 207 • NeetCode • 428,818 views views
Watch 9 more video solutions →Practice Course Schedule II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor