Course Schedule

Determine if you can finish all courses given prerequisite relationships using topological sorting

Language Selection

Choose your preferred programming language

Showing: Python

Course Schedule

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return true if you can finish all courses. Otherwise, return false.

Input/Output Specifications

Input:
- numCourses: An integer representing the total number of courses
- prerequisites: A 2D array where each element [a, b] means course a requires course b
Output: A boolean indicating whether all courses can be completed
Constraints:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- All pairs prerequisites[i] are unique

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are 2 courses. To take course 1, you need to finish course 0. This is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are 2 courses. To take course 1, you need course 0, and to take course 0, you need course 1. This creates a cycle.

Example 3:

Input: numCourses = 3, prerequisites = [[1,0],[2,1]]
Output: true
Explanation: Course dependency: 0 → 1 → 2. This is a valid topological order.

Example 4:

Input: numCourses = 4, prerequisites = []
Output: true
Explanation: No prerequisites means all courses can be taken independently.

Solution Approaches

Approach 1: DFS Cycle Detection (Optimal)

Use depth-first search to detect cycles in the directed graph formed by course prerequisites.

Algorithm Explanation

Build Graph: Create adjacency list representation of prerequisite relationships
State Tracking: Use three states for each node:
- WHITE (0): Unvisited
- GRAY (1): Currently being processed (in DFS path)
- BLACK (2): Completely processed
DFS Traversal: For each unvisited node:
- Mark as GRAY (visiting)
- Visit all neighbors recursively
- If neighbor is GRAY, cycle detected
- Mark as BLACK when done
Result: No cycles means all courses can be completed

Implementation

Python:

class Solution:
    """
    DFS cycle detection approach for course schedule
    Time: O(V + E) where V is courses, E is prerequisites
    Space: O(V + E) for adjacency list and recursion stack
    """
    
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # Build adjacency list
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)
        
        # States: 0=white (unvisited), 1=gray (visiting), 2=black (visited)
        state = [0] * numCourses
        
        def has_cycle(node):
            if state[node] == 1:  # Gray - cycle detected
                return True
            if state[node] == 2:  # Black - already processed
                return False
            
            # Mark as visiting (gray)
            state[node] = 1
            
            # Visit all neighbors
            for neighbor in graph[node]:
                if has_cycle(neighbor):
                    return True
            
            # Mark as visited (black)
            state[node] = 2
            return False
        
        # Check each unvisited node for cycles
        for course in range(numCourses):
            if state[course] == 0 and has_cycle(course):
                return False
        
        return True

Java:

class Solution {
    /**
     * DFS cycle detection approach for course schedule
     * Time: O(V + E) where V is courses, E is prerequisites
     * Space: O(V + E) for adjacency list and recursion stack
     */
    
    private List<List<Integer>> graph;
    private int[] state;
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build adjacency list
        graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] prereq : prerequisites) {
            graph.get(prereq[1]).add(prereq[0]);
        }
        
        // States: 0=white, 1=gray, 2=black
        state = new int[numCourses];
        
        // Check each unvisited node for cycles
        for (int course = 0; course < numCourses; course++) {
            if (state[course] == 0 && hasCycle(course)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean hasCycle(int node) {
        if (state[node] == 1) { // Gray - cycle detected
            return true;
        }
        if (state[node] == 2) { // Black - already processed
            return false;
        }
        
        // Mark as visiting (gray)
        state[node] = 1;
        
        // Visit all neighbors
        for (int neighbor : graph.get(node)) {
            if (hasCycle(neighbor)) {
                return true;
            }
        }
        
        // Mark as visited (black)
        state[node] = 2;
        return false;
    }
}

Go:

// canFinish - DFS cycle detection approach for course schedule
// Time: O(V + E) where V is courses, E is prerequisites
// Space: O(V + E) for adjacency list and recursion stack
func canFinish(numCourses int, prerequisites [][]int) bool {
    // Build adjacency list
    graph := make([][]int, numCourses)
    for _, prereq := range prerequisites {
        course, dep := prereq[0], prereq[1]
        graph[dep] = append(graph[dep], course)
    }
    
    // States: 0=white, 1=gray, 2=black
    state := make([]int, numCourses)
    
    var hasCycle func(int) bool
    hasCycle = func(node int) bool {
        if state[node] == 1 { // Gray - cycle detected
            return true
        }
        if state[node] == 2 { // Black - already processed
            return false
        }
        
        // Mark as visiting (gray)
        state[node] = 1
        
        // Visit all neighbors
        for _, neighbor := range graph[node] {
            if hasCycle(neighbor) {
                return true
            }
        }
        
        // Mark as visited (black)
        state[node] = 2
        return false
    }
    
    // Check each unvisited node for cycles
    for course := 0; course < numCourses; course++ {
        if state[course] == 0 && hasCycle(course) {
            return false
        }
    }
    
    return true
}

JavaScript:

/**
 * DFS cycle detection approach for course schedule
 * Time: O(V + E) where V is courses, E is prerequisites
 * Space: O(V + E) for adjacency list and recursion stack
 */
function canFinish(numCourses, prerequisites) {
    // Build adjacency list
    const graph = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
    }
    
    // States: 0=white, 1=gray, 2=black
    const state = new Array(numCourses).fill(0);
    
    function hasCycle(node) {
        if (state[node] === 1) { // Gray - cycle detected
            return true;
        }
        if (state[node] === 2) { // Black - already processed
            return false;
        }
        
        // Mark as visiting (gray)
        state[node] = 1;
        
        // Visit all neighbors
        for (const neighbor of graph[node]) {
            if (hasCycle(neighbor)) {
                return true;
            }
        }
        
        // Mark as visited (black)
        state[node] = 2;
        return false;
    }
    
    // Check each unvisited node for cycles
    for (let course = 0; course < numCourses; course++) {
        if (state[course] === 0 && hasCycle(course)) {
            return false;
        }
    }
    
    return true;
}

C#:

public class Solution {
    /// <summary>
    /// DFS cycle detection approach for course schedule
    /// Time: O(V + E) where V is courses, E is prerequisites
    /// Space: O(V + E) for adjacency list and recursion stack
    /// </summary>
    
    private List<List<int>> graph;
    private int[] state;
    
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        // Build adjacency list
        graph = new List<List<int>>();
        for (int i = 0; i < numCourses; i++) {
            graph.Add(new List<int>());
        }
        
        foreach (var prereq in prerequisites) {
            graph[prereq[1]].Add(prereq[0]);
        }
        
        // States: 0=white, 1=gray, 2=black
        state = new int[numCourses];
        
        // Check each unvisited node for cycles
        for (int course = 0; course < numCourses; course++) {
            if (state[course] == 0 && HasCycle(course)) {
                return false;
            }
        }
        
        return true;
    }
    
    private bool HasCycle(int node) {
        if (state[node] == 1) { // Gray - cycle detected
            return true;
        }
        if (state[node] == 2) { // Black - already processed
            return false;
        }
        
        // Mark as visiting (gray)
        state[node] = 1;
        
        // Visit all neighbors
        foreach (int neighbor in graph[node]) {
            if (HasCycle(neighbor)) {
                return true;
            }
        }
        
        // Mark as visited (black)
        state[node] = 2;
        return false;
    }
}

Approach 2: Kahn’s Algorithm (BFS Topological Sort)

Use Kahn’s algorithm to perform topological sorting using BFS and in-degree counting.

Algorithm Explanation

Calculate In-degrees: Count incoming edges for each node
Initialize Queue: Add all nodes with in-degree 0 to queue
Process Queue: While queue is not empty:
- Remove node from queue and increment processed count
- For each neighbor, decrease its in-degree
- If neighbor’s in-degree becomes 0, add to queue
Validate: If processed count equals total courses, no cycle exists

Implementation

Python:

from collections import deque

class Solution:
    """
    Kahn's algorithm (BFS topological sort) for course schedule
    Time: O(V + E) where V is courses, E is prerequisites
    Space: O(V + E) for adjacency list and queue
    """
    
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # Build adjacency list and calculate in-degrees
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
        
        # Initialize queue with nodes having in-degree 0
        queue = deque()
        for course in range(numCourses):
            if in_degree[course] == 0:
                queue.append(course)
        
        processed = 0
        
        # Process nodes in topological order
        while queue:
            current = queue.popleft()
            processed += 1
            
            # Process all neighbors
            for neighbor in graph[current]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        # All courses can be finished if all nodes are processed
        return processed == numCourses

Java:

class Solution {
    /**
     * Kahn's algorithm (BFS topological sort) for course schedule
     * Time: O(V + E) where V is courses, E is prerequisites
     * Space: O(V + E) for adjacency list and queue
     */
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build adjacency list and calculate in-degrees
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] prereq : prerequisites) {
            graph.get(prereq[1]).add(prereq[0]);
            inDegree[prereq[0]]++;
        }
        
        // Initialize queue with nodes having in-degree 0
        Queue<Integer> queue = new LinkedList<>();
        for (int course = 0; course < numCourses; course++) {
            if (inDegree[course] == 0) {
                queue.offer(course);
            }
        }
        
        int processed = 0;
        
        // Process nodes in topological order
        while (!queue.isEmpty()) {
            int current = queue.poll();
            processed++;
            
            // Process all neighbors
            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // All courses can be finished if all nodes are processed
        return processed == numCourses;
    }
}

Complexity Analysis

DFS Approach

Time Complexity: O(V + E) where V is number of courses and E is number of prerequisites
Space Complexity: O(V + E) for adjacency list and O(V) for recursion stack = O(V + E)

BFS Approach (Kahn’s Algorithm)

Time Complexity: O(V + E) where V is number of courses and E is number of prerequisites
Space Complexity: O(V + E) for adjacency list and O(V) for queue = O(V + E)

Key Insights

Graph Representation: Course prerequisites form a directed graph
Cycle Detection: Courses can be completed if and only if there are no cycles
Topological Ordering: Valid course schedule corresponds to topological ordering
Multiple Approaches: Both DFS and BFS can solve this efficiently

Edge Cases

No Prerequisites: Empty prerequisites array - all courses can be taken
Self-Loop: Course requires itself as prerequisite (invalid input per constraints)
Simple Cycle: Two courses requiring each other
Complex Cycle: Multiple courses forming a longer cycle
Disconnected Components: Multiple independent groups of courses
Single Course: Only one course with no prerequisites

Test Cases

# Test cases for validation
def test_course_schedule():
    solution = Solution()
    
    # Test case 1: Valid linear dependency
    assert solution.canFinish(3, [[1,0],[2,1]]) == True
    
    # Test case 2: Simple cycle
    assert solution.canFinish(2, [[1,0],[0,1]]) == False
    
    # Test case 3: No prerequisites
    assert solution.canFinish(3, []) == True
    
    # Test case 4: Valid complex dependency
    assert solution.canFinish(4, [[1,0],[2,0],[3,1],[3,2]]) == True
    
    # Test case 5: Complex cycle
    assert solution.canFinish(4, [[1,0],[2,1],[3,2],[1,3]]) == False
    
    # Test case 6: Single course
    assert solution.canFinish(1, []) == True

Follow-up Questions

Course Schedule II: Return the actual ordering of courses if possible
Minimum Semesters: Find minimum number of semesters to complete all courses
Course Dependencies: Find all courses that depend on a given course
Parallel Courses: Determine maximum courses that can be taken simultaneously

Common Mistakes

Wrong Graph Direction: Building edges in the wrong direction (prerequisite → course vs course → prerequisite)
Missing Cycle Detection: Not properly detecting back edges in DFS
State Management: Incorrectly managing the three-color state in DFS
In-degree Calculation: Errors in calculating or updating in-degrees in BFS approach

Interview Tips

Clarify Graph Direction: Confirm which direction the prerequisite relationship represents
Choose Approach: Both DFS and BFS work - choose based on familiarity
Explain Intuition: Relate the problem to topological sorting and cycle detection
Handle Edge Cases: Consider empty prerequisites and disconnected components
Code Incrementally: Start with graph building, then add cycle detection logic
Optimize Space: Mention that we can sometimes optimize space by reusing input arrays