Watch 10 video solutions for Course Schedule II, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by NeetCode has 428,818 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |