-
Notifications
You must be signed in to change notification settings - Fork 0
118 — Course Schedule II
LeetCode 210 · Medium. Same setup as Course Schedule: numCourses courses, prerequisites[i] = [a, b] meaning b must come before a. Instead of just yes/no, return one valid ordering in which all courses can be taken, or an empty array if none exists.
Course Schedule only asked "does a valid order exist?" — this asks for the order itself. That's exactly what a topological sort produces: an ordering of a directed graph's vertices such that every edge b → a places b before a in the output. The previous chapter reached for Kahn's algorithm (BFS-flavored: process courses with zero remaining prerequisites, layer by layer). This time, reach for the other classic topological sort: DFS-based, where a course is appended to the order only after all of its prerequisites have been fully explored — postorder DFS, reversed... except appending on the way out of the recursion already produces the right order directly, no reversal needed.
"Return a valid order, not just whether one exists" is the cue to reach for DFS-based topological sort: recurse into a course's prerequisites first, and only append the course to the result after returning from all of them — with a three-state marker (unvisited / in-progress / done) to catch cycles along the way.
DFS-based topological sort, correct in shape, but tracking visited/in-progress state with linear-scan arrays (.contains) instead of an O(1)-indexed state array.
func findOrderBruteForce(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var adjacency = Array(repeating: [Int](), count: numCourses)
for edge in prerequisites {
adjacency[edge[0]].append(edge[1]) // course -> its prerequisites
}
var visited: [Int] = [] // linear-scan "done" set
var inStack: [Int] = [] // linear-scan "currently on recursion path" set
var order: [Int] = []
var hasCycle = false
func dfs(_ course: Int) {
if hasCycle { return }
if inStack.contains(course) { hasCycle = true; return }
if visited.contains(course) { return }
inStack.append(course)
for prereq in adjacency[course] {
dfs(prereq)
if hasCycle { return }
}
inStack.removeAll { $0 == course }
visited.append(course)
order.append(course) // prerequisites are appended before the course itself
}
for course in 0..<numCourses where !visited.contains(course) {
dfs(course)
if hasCycle { return [] }
}
return order
}Big-O: O(V² + V·E) — every dfs call performs up to two O(V) linear scans (inStack.contains, visited.contains), across O(V + E) total calls.
Same DFS-based topological sort, but state is tracked with an O(1)-indexed three-state array: 0 unvisited, 1 in-progress (on the current recursion path — finding this again means a cycle), 2 done.
func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var adjacency = Array(repeating: [Int](), count: numCourses)
for edge in prerequisites {
adjacency[edge[0]].append(edge[1])
}
var state = Array(repeating: 0, count: numCourses) // 0 unvisited, 1 in-progress, 2 done
var order: [Int] = []
var hasCycle = false
func dfs(_ course: Int) {
if hasCycle { return }
if state[course] == 1 { hasCycle = true; return }
if state[course] == 2 { return }
state[course] = 1
for prereq in adjacency[course] {
dfs(prereq)
if hasCycle { return }
}
state[course] = 2
order.append(course)
}
for course in 0..<numCourses where state[course] == 0 {
dfs(course)
if hasCycle { return [] }
}
return order
}
// smoke test
print(findOrder(2, [[1,0]])) // [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])) // a valid order, e.g. [0, 2, 1, 3]
print(findOrder(2, [[0,1],[1,0]])) // [] - cycleBig-O: O(V + E) time — each vertex's state is checked and set in O(1), each vertex is fully explored once, each edge once. O(V) space for state, order, and the recursion stack.
Both versions perform the exact same DFS: recurse into prerequisites first, append a course to order only once all of its dependencies are resolved, and bail out the instant a course is found already "in progress" on the current recursion path (a cycle). The only cost difference is how "in progress" and "done" get checked — the brute force answers both questions by scanning a growing list, while the optimal version answers them with a single array read at a known index. It's the identical incremental-vs-recompute contrast that runs through every problem in this chapter, just applied to DFS state instead of BFS in-degree counts.
- Graphs — cycle detection via a three-state DFS marker (unvisited/in-progress/done) is the standard technique for directed-graph cycle detection.
- Topological Sort — DFS-based topological sort (append on the way out of the recursion) is the second of the two canonical topological sort techniques, alongside Kahn's algorithm from Course Schedule.
-
DFS and Backtracking —
dfshere recurses fully into every prerequisite before doing its own work, the same "resolve children before self" recursive shape used throughout this wiki.
Course Schedule II is DFS that appends on the way out, not the way in — a course only joins the order once every one of its prerequisites has already finished, and finding a course still "in progress" means a cycle.
- Why does appending
coursetoorderafter the loop overadjacency[course](rather than before) guarantee prerequisites always appear earlier in the final array? - Why are three states needed (unvisited / in-progress / done) instead of just two (visited / unvisited) — what cycle would a plain visited-set DFS fail to catch?
- Trace
findOrderby hand onnumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. In what order doesstate[course]become2for each course, and does that match one of the outputs listed in the smoke test?
⬅️ Previous: Course Schedule · Next: Redundant Connection ➡️