210. Course Schedule II (Topological Sort) - Leetcode Solution
Solution code💡 Step-by-Step Thought Process
- Understand the problem: Find a valid order to take all courses given prerequisites, returning an empty list if impossible.
- Create an adjacency list using a defaultdict to store the graph, where each course maps to its prerequisites.
- Initialize an empty list order to store the course order.
- Initialize a states array with UNVISITED (0) for each course to track visit status.
- Define a DFS function that takes a node (course) and returns False if a cycle is detected, True otherwise.
- In DFS, if the node is VISITING (1), a cycle is detected, return False.
- If the node is VISITED (2), return True as it’s already processed.
- Mark the node as VISITING, then recursively check all its neighbors (prerequisites).
- If any neighbor returns False, return False.
- Mark the node as VISITED, append it to order, and return True.
- Run DFS for each course; if any returns False, return an empty list.
- Return the order list.
Code Solution
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
order = []
g = defaultdict(list)
for a, b in prerequisites:
g[a].append(b)
UNVISITED, VISITING, VISITED = 0, 1, 2
states = [UNVISITED] * numCourses
def dfs(i):
if states[i] == VISITING:
return False
elif states[i] == VISITED:
return True
states[i] = VISITING
for nei in g[i]:
if not dfs(nei):
return False
states[i] = VISITED
order.append(i)
return True
for i in range(numCourses):
if not dfs(i):
return []
return order # Time: O(V + E), Space: O(V + E)
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> order, inDegree(numCourses, 0);
unordered_map<int, vector<int>> map;
queue<int> queue;
for (auto& pre : prerequisites) {
int target = pre[0], preCourse = pre[1];
map[preCourse].push_back(target);
inDegree[target] += 1;
}
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
queue.push(i);
}
}
while (!queue.empty()) {
int node = queue.front();
queue.pop();
order.push_back(node);
if (map.find(node) != map.end()) {
for (int target : map[node]) {
inDegree[target] -= 1;
if (inDegree[target] == 0) {
queue.push(target);
}
}
}
}
return order.size() == numCourses ? order : vector<int>();
}
};class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] order = new int[numCourses];
int[] inDegree = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
// Initialize the graph
for (int[] pre : prerequisites) {
int target = pre[0], preCourse = pre[1];
map.computeIfAbsent(preCourse, k -> new ArrayList<>()).add(target);
inDegree[target] += 1;
}
// Find all courses with no prerequisites
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int index = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
order[index++] = node;
if (map.containsKey(node)) {
for (int target : map.get(node)) {
inDegree[target] -= 1;
if (inDegree[target] == 0) {
queue.offer(target);
}
}
}
}
return index == numCourses ? order : new int[0];
}
}var findOrder = function (numCourses, prerequisites) {
const order = [], queue = []
const inDegree = new Array(numCourses).fill(0)
const map = new Map()
for (let [target, pre] of prerequisites) {
map.has(pre) ? map.get(pre).push(target) : map.set(pre, [target])
inDegree[target] += 1
}
console.log(map)
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.push(i)
}
}
while (queue.length != 0) {
let node = queue.shift()
order.push(node)
console.log(node, map.get(node))
if (map.has(node)) {
for (let tar of map.get(node)) {
inDegree[tar] -= 1
if (inDegree[tar] == 0) {
queue.push(tar)
}
}
}
}
return order.length==numCourses?order:[]
};Detailed Explanation
What Is the Course Schedule II Problem?
The Course Schedule II problem asks you to return a valid order in which to complete all courses given a list of prerequisites. If it’s impossible to complete all courses due to a cycle in the course dependencies, return an empty list.
Topological Sort Approach for Course Scheduling
This problem is a classic application of topological sorting in a directed graph. Each course is a node, and each prerequisite is a directed edge. To solve this, we use depth-first search (DFS) to build a valid course order and detect cycles.
How to Solve Course Schedule II Using DFS
Here is a step-by-step breakdown of how to solve the problem using DFS and a cycle detection strategy:
- Use a hash map to build an adjacency list from the prerequisites.
- Track each course’s visit state with an array: UNVISITED (0), VISITING (1), and VISITED (2).
- Perform DFS traversal for each course:
- If the course is VISITING again, a cycle exists → return False.
- If the course is VISITED, return True to avoid redundant work.
- Mark the course as VISITING and recursively visit all prerequisites.
- Once all neighbors are explored, mark the course as VISITED and append it to the course order.
- Reverse the result list to get the correct topological sort order.
Why Topological Sorting Works for Course Prerequisites
In a valid course order, all prerequisites must appear before the dependent course. Using post-order traversal during DFS naturally builds this order. Reversing the result ensures each course comes after its dependencies. If a cycle is found, we can’t finish all courses, and we return an empty list.
Time and Space Complexity of the Solution
Time Complexity: O(V + E), where V is the number of courses and E is the number of prerequisites. Each node and edge is visited once.
Space Complexity: O(V + E), due to the adjacency list and recursive call stack.
Conclusion: Solving Course Schedule II Efficiently
The DFS-based topological sort is an efficient way to solve the Course Schedule II problem. It detects cycles in course prerequisites and builds a valid course completion order. This approach is scalable, fast, and leverages key graph theory principles used in many scheduling and dependency resolution problems.