Course Schedule II

Problem Statement

You are given a number of courses labeled from 0 to numCourses - 1 and a list of prerequisite pairs prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before taking course ai. Return the ordering of courses you should take to finish all courses. Return an empty array if impossible.

Key Insight

• This is a topological sorting problem on a directed acyclic graph (DAG).
• If there’s a cycle, return an empty array.
• Both DFS and BFS (Kahn’s algorithm) can produce valid topological orderings.

Examples

numCourses	prerequisites	Output	Explanation
2	[[1,0]]	[0,1]	Take course 0, then course 1
4	[[1,0],[2,0],[3,1],[3,2]]	[0,2,1,3] or [0,1,2,3]	Valid topological order (multiple valid orderings exist)
3	[[1,0],[0,1]]	[]	Circular dependency — impossible
1	[]	[0]	No prerequisites, single course

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi (no self-loops)
• All (ai, bi) are unique

Real-World Applications

Where this pattern appears

• Social network analysis and friend recommendations
• Route planning and GPS navigation
• Dependency resolution and build systems
• Recommendation systems and collaborative filtering

Complexity Comparison

Approach	Time	Space	Notes
DFS Topological	O(n)	O(n)	First approach
BFS Kahn	O(n)	O(n)	Second approach

Approach 1: DFS Topological

★ Recommended

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

course_schedule_ii_dfs_topological.py

def findOrder(numCourses, prerequisites):
    """DFS topological sort to get course order."""
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    state = [0] * numCourses
    order = []

    def dfs(course):
        if state[course] == 1:
            return False
        if state[course] == 2:
            return True

        state[course] = 1
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        state[course] = 2
        order.append(course)
        return True

    for i in range(numCourses):
        if not dfs(i):
            return []
    return order

C++

course_schedule_ii_dfs_topological.cpp

class Solution {
    // TODO: Implement
};

Java

CourseScheduleIiDfsTopological.java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] state = new int[numCourses];
        int[][] graph = new int[numCourses][];
        int[] size = new int[numCourses];

        for (int[] pre : prerequisites) size[pre[0]]++;
        for (int i = 0; i < numCourses; i++) graph[i] = new int[size[i]];

        size = new int[numCourses];
        for (int[] pre : prerequisites) graph[pre[0]][size[pre[0]]++] = pre[1];

        int[] order = new int[numCourses];
        int[] idx = {numCourses - 1};

        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, state, i, order, idx)) return new int[]{};
        }
        return order;
    }

    private boolean dfs(int[][] graph, int[] state, int course, int[] order, int[] idx) {
        if (state[course] == 1) return false;
        if (state[course] == 2) return true;

        state[course] = 1;
        for (int prereq : graph[course]) {
            if (!dfs(graph, state, prereq, order, idx)) return false;
        }
        state[course] = 2;
        order[idx[0]--] = course;
        return true;
    }
}

JavaScript

course_schedule_ii_dfs_topological.js

// Graph solution implementation
function solve() {
    // TODO: Implement
}

Rust

course_schedule_ii_dfs_topological.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

course_schedule_ii_dfs_topological.go

package main

// TODO: Implement solution

Approach 2: BFS Kahn

✓ Simple

⏱ Time O(n) 💾 Space O(n)

Solution Code

Python

course_schedule_ii_bfs_kahn.py

"""
Solution for Course Schedule II
"""

def solve():
    """Implementation for approach 3 of Course Schedule II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

course_schedule_ii_bfs_kahn.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Course Schedule II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

CourseScheduleIiBfsKahn.java

/**
 * Solution for Course Schedule II
 * Approach 3
 */
public class CourseScheduleIiBfsIterative {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

course_schedule_ii_bfs_kahn.js

/**
 * Solution for Course Schedule II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

course_schedule_ii_bfs_kahn.rs

/// Solution for Course Schedule II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

course_schedule_ii_bfs_kahn.go

package main

import "fmt"

// Solution for Course Schedule II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Interview Tips

Key trade-offs to discuss

• Approach 1 vs Approach 2 trade-offs
• Edge cases and how to handle them
• Follow-up questions

← Previous
#207 Course Schedule Next
#909 Snakes and Ladders →