Course Schedule

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 true if you can finish all courses, otherwise return false.

Key Insight

• This is a cycle detection problem in a directed graph
• If there’s a cycle in the prerequisite graph, it’s impossible to complete all courses
• Think about topological sorting — a valid ordering exists only if the graph is acyclic
• Both DFS and BFS (Kahn’s algorithm) can detect cycles effectively

Examples

numCourses	prerequisites	Output	Explanation
2	[[1,0]]	true	Take course 0 first, then course 1
2	[[1,0],[0,1]]	false	Circular dependency: course 0 requires 1, course 1 requires 0
3	[[0,1],[0,2],[1,2]]	true	Take course 2, then 1, then 0
4	[[1,0],[2,0],[3,1],[3,2]]	true	Valid topological order: 0 → 1 → 2 → 3 and 0 → 2 → 3

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All values are unique

Real-World Applications

Where this pattern appears

• Build system dependency resolution — checking if build targets can be compiled without circular dependencies
• Task scheduling — determining if all tasks can be executed respecting their prerequisites
• Curriculum planning — validating course requirements don’t have circular dependencies
• Software module loading — ensuring module imports don’t form circular reference chains

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_dfs_topological.py

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

    state = [0] * numCourses  # 0: unvisited, 1: visiting, 2: visited

    def has_cycle(course):
        if state[course] == 1:
            return True  # Cycle detected
        if state[course] == 2:
            return False  # Already processed

        state[course] = 1
        for prereq in graph[course]:
            if has_cycle(prereq):
                return True
        state[course] = 2
        return False

    for i in range(numCourses):
        if has_cycle(i):
            return False
    return True

C++

course_schedule_dfs_topological.cpp

class Solution {
public:
    // TODO: Implement solution
};

Java

CourseScheduleDfsTopological.java

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();

        for (int[] prereq : prerequisites) {
            graph[prereq[0]].add(prereq[1]);
        }

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

    private boolean dfs(int course, List<Integer>[] graph, int[] state) {
        if (state[course] == 1) return false;
        if (state[course] == 2) return true;

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

System.out.println(new Solution().canFinish(2, new int[][]{{1,0}}));

JavaScript

course_schedule_dfs_topological.js

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

Rust

course_schedule_dfs_topological.rs

impl Solution {
    // TODO: Implement
}

pub struct Solution;

Go

course_schedule_dfs_topological.go

package main

// TODO: Implement solution

Approach 2: BFS Kahn

✓ Simple

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

Solution Code

Python

course_schedule_bfs_kahn.py

"""
Solution for Course Schedule
"""

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

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

C++

course_schedule_bfs_kahn.cpp

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

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

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

Java

CourseScheduleBfsKahn.java

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();

        for (int[] prereq : prerequisites) {
            graph[prereq[1]].add(prereq[0]);
            inDegree[prereq[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.add(i);
        }

        int processed = 0;
        while (!queue.isEmpty()) {
            int course = queue.remove();
            processed++;

            for (int nextCourse : graph[course]) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    queue.add(nextCourse);
                }
            }
        }

        return processed == numCourses;
    }
}

System.out.println(new Solution().canFinish(2, new int[][]{{1,0}}));

JavaScript

course_schedule_bfs_kahn.js

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

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

module.exports = solve;

Rust

course_schedule_bfs_kahn.rs

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

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

Go

course_schedule_bfs_kahn.go

package main

import "fmt"

// Solution for Course Schedule
// 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
#399 Evaluate Division Next
#210 Course Schedule II →