Introduction to Course Schedule II
Course Schedule II is a classic graph problem frequently encountered in coding interviews and algorithm challenges. The problem asks you to determine a valid ordering of courses given their prerequisites. If no valid ordering exists (because of a cycle in the dependency graph), you must return an empty array.
Formally, you are given numCourses labeled from 0 to numCourses - 1, and an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b before course a. Your task is to return any valid ordering of all courses that satisfies all prerequisite constraints.
Why This Problem Matters
This problem is the canonical example of topological sorting, a fundamental algorithm with real-world applications:
- Build systems — determining the order in which modules or packages should be compiled based on dependencies.
- Task scheduling — ordering jobs in a pipeline where some jobs depend on the output of others.
- Course planning — helping students plan a sequence of classes that respects prerequisite chains.
- Package managers — installing libraries in the correct dependency order.
- Data pipeline orchestration — tools like Airflow or dbt rely on DAG-based ordering.
Mastering this problem teaches you how to model relationships as directed graphs, detect cycles, and produce valid orderings — skills that translate directly to systems design and infrastructure work.
Understanding the Underlying Concepts
Directed Acyclic Graphs (DAGs)
The courses and their prerequisites form a directed graph. Each course is a node, and each prerequisite pair [a, b] is a directed edge from b to a (meaning b must come before a).
A valid course ordering exists if and only if the graph is a DAG — a Directed Acyclic Graph. If the graph contains a cycle, no valid ordering is possible because you would have a circular dependency that can never be satisfied.
Topological Sorting
A topological sort of a DAG is a linear ordering of its vertices such that for every directed edge u → v, vertex u appears before v in the ordering. There are two primary algorithms for topological sorting:
- Kahn's Algorithm (BFS-based) — repeatedly removes nodes with no incoming edges.
- DFS-based Algorithm — performs a depth-first traversal and reverses the finish order.
We will implement both in Go so you can choose the approach that best fits your style and constraints.
Approach 1: Kahn's Algorithm (BFS)
How Kahn's Algorithm Works
Kahn's algorithm is intuitive and naturally detects cycles. The steps are:
- Compute the in-degree (number of incoming edges) for every node.
- Initialize a queue with all nodes that have an in-degree of
0. - While the queue is not empty, remove a node, append it to the result, and decrement the in-degree of its neighbors. If any neighbor's in-degree becomes
0, add it to the queue. - If the result contains all nodes, return it. Otherwise, a cycle exists and you return an empty array.
Go Implementation
package main
import "fmt"
func findOrder(numCourses int, prerequisites [][]int) []int {
// Build adjacency list and in-degree array
adj := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for _, prereq := range prerequisites {
course, prereqCourse := prereq[0], prereq[1]
adj[prereqCourse] = append(adj[prereqCourse], course)
inDegree[course]++
}
// Initialize queue with all courses that have no prerequisites
queue := []int{}
for i := 0; i < numCourses; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
order := []int{}
for len(queue) > 0 {
// Dequeue the front element
current := queue[0]
queue = queue[1:]
order = append(order, current)
// Reduce in-degree of neighbors
for _, neighbor := range adj[current] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
// If we processed all courses, return the order; otherwise a cycle exists
if len(order) == numCourses {
return order
}
return []int{}
}
func main() {
// Example 1: valid ordering exists
result1 := findOrder(4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}})
fmt.Println("Example 1 order:", result1)
// Example 2: single course, no prerequisites
result2 := findOrder(1, [][]int{})
fmt.Println("Example 2 order:", result2)
// Example 3: cycle exists, no valid ordering
result3 := findOrder(2, [][]int{{0, 1}, {1, 0}})
fmt.Println("Example 3 order:", result3)
}
When you run this program, the output will look like:
Example 1 order: [0 1 2 3]
Example 2 order: [0]
Example 3 order: []
Note that for Example 1, [0 2 1 3] is also a valid answer. Topological orderings are not necessarily unique — any valid ordering is acceptable.
Complexity Analysis
- Time complexity: O(V + E), where V is the number of courses and E is the number of prerequisite pairs. We visit each node and each edge exactly once.
- Space complexity: O(V + E) for the adjacency list, in-degree array, queue, and result array.
Approach 2: DFS-Based Topological Sort
How the DFS Approach Works
The DFS approach uses three states for each node to detect cycles:
0— unvisited1— currently being visited (in the current DFS path)2— fully processed
For each unvisited node, we start a DFS. If we encounter a node that is currently being visited (state 1), we have detected a cycle. After fully exploring a node's neighbors, we mark it as processed (state 2) and add it to the front of the result (or append and reverse at the end).
Go Implementation
package main
import "fmt"
func findOrderDFS(numCourses int, prerequisites [][]int) []int {
// Build adjacency list
adj := make([][]int, numCourses)
for _, prereq := range prerequisites {
course, prereqCourse := prereq[0], prereq[1]
adj[prereqCourse] = append(adj[prereqCourse], course)
}
// State: 0 = unvisited, 1 = visiting, 2 = visited
state := make([]int, numCourses)
order := []int{}
var dfs func(node int) bool
dfs = func(node int) bool {
if state[node] == 1 {
// Cycle detected
return false
}
if state[node] == 2 {
// Already processed
return true
}
// Mark as visiting
state[node] = 1
for _, neighbor := range adj[node] {
if !dfs(neighbor) {
return false
}
}
// Mark as visited and add to order
state[node] = 2
order = append(order, node)
return true
}
// Run DFS from every unvisited node
for i := 0; i < numCourses; i++ {
if state[i] == 0 {
if !dfs(i) {
return []int{}
}
}
}
// Reverse the order since we appended after processing children
reversed := make([]int, numCourses)
for i := 0; i < numCourses; i++ {
reversed[i] = order[numCourses-1-i]
}
return reversed
}
func main() {
result := findOrderDFS(4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}})
fmt.Println("DFS order:", result)
}
The DFS approach has the same time and space complexity as Kahn's algorithm: O(V + E) for both. The choice between them often comes down to personal preference and the specific requirements of the problem you are solving.
Comparing the Two Approaches
When to Use Kahn's Algorithm
- You want a more iterative, queue-based solution that is easier to reason about step by step.
- You need to detect cycles naturally — if the result does not contain all nodes, a cycle exists.
- You want to process nodes level by level, which can be useful for layered scheduling.
When to Use DFS
- You prefer a recursive solution that mirrors the structure of the graph.
- You are already using DFS for other parts of your solution and want consistency.
- You need fine-grained control over when nodes are marked as processed.
In practice, both approaches perform equally well for Course Schedule II. Kahn's algorithm tends to be slightly more popular in interview settings because the cycle detection is built into the final length check, making the logic easy to explain.
Best Practices
1. Always Validate Input
Before building your graph, consider edge cases such as numCourses = 0 or an empty prerequisites array. Both algorithms handle these gracefully, but being explicit about your assumptions makes your code more robust.
2. Pre-allocate Slices Where Possible
In Go, pre-allocating slices with make([]int, 0, numCourses) avoids repeated reallocations as you append elements. This is a small optimization that can matter for large inputs.
order := make([]int, 0, numCourses)
3. Use Clear Variable Names
Names like adj, inDegree, and order make your intent obvious. Avoid single-letter variables except for simple loop counters.
4. Test with Diverse Cases
Make sure your solution handles these scenarios:
- A graph with no edges (all courses are independent).
- A linear chain of prerequisites (e.g., 0 → 1 → 2 → 3).
- A graph with a cycle (should return an empty array).
- A disconnected graph with multiple independent components.
- A single course with no prerequisites.
5. Avoid Stack Overflow with Deep Recursion
The DFS approach uses recursion, which can cause stack overflow for very deep graphs. If you expect extremely large inputs, prefer Kahn's iterative approach or convert the DFS to an explicit stack-based iteration.
Common Pitfalls
Confusing Edge Direction
A frequent mistake is building the adjacency list with edges in the wrong direction. Remember that [a, b] means b must be taken before a, so the edge goes from b to a. If you reverse this, your in-degrees and traversal will be incorrect.
Forgetting to Check the Final Length
In Kahn's algorithm, it is easy to forget the final check that compares len(order) with numCourses. Without this check, you might return a partial ordering when a cycle exists, which would be incorrect.
Mutating Shared State
If you are writing a function that will be called multiple times, ensure you create fresh data structures for each call. Reusing slices or maps across calls can lead to subtle bugs.
Putting It All Together
Here is a final, polished version of the Kahn's algorithm solution with pre-allocation and clear structure:
package main
import "fmt"
func findOrder(numCourses int, prerequisites [][]int) []int {
adj := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for _, p := range prerequisites {
course, prereq := p[0], p[1]
adj[prereq] = append(adj[prereq], course)
inDegree[course]++
}
queue := make([]int, 0, numCourses)
for i := 0; i < numCourses; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
order := make([]int, 0, numCourses)
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
order = append(order, curr)
for _, next := range adj[curr] {
inDegree[next]--
if inDegree[next] == 0 {
queue = append(queue, next)
}
}
}
if len(order) != numCourses {
return []int{}
}
return order
}
func main() {
tests := []struct {
numCourses int
prerequisites [][]int
}{
{4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}}},
{1, [][]int{}},
{2, [][]int{{0, 1}, {1, 0}}},
{3, [][]int{{1, 0}, {2, 1}}},
}
for _, t := range tests {
fmt.Printf("numCourses=%d, prereqs=%v => %v\n",
t.numCourses, t.prerequisites, findOrder(t.numCourses, t.prerequisites))
}
}
Conclusion
Course Schedule II is a deceptively simple problem that opens the door to understanding topological sorting, cycle detection, and graph traversal in general. By implementing both Kahn's BFS-based algorithm and the DFS-based approach in Go, you now have two reliable tools for solving any problem that involves ordering tasks with dependencies. Remember to validate your inputs, pre-allocate slices for performance, test against edge cases including cycles, and choose the algorithm that best fits your constraints. With these patterns in your toolkit, you will be well-prepared to tackle not only this problem but also the many real-world systems that rely on dependency resolution and task ordering.