LeetCode Course Schedule I Explained: The Art of Cycle Detection

The Course Schedule I problem is a classic challenge in graph theory and algorithm design, frequently appearing in technical interviews and competitive programming. It asks us to determine whether all courses in a curriculum can be completed given a set of prerequisites. At its core, the problem translates into detecting cycles in a directed graph, where courses are nodes, and prerequisites form directed edges. This problem serves as an excellent introduction to key graph traversal techniques like Depth-First Search (DFS) and Breadth-First Search (BFS), while also showcasing the importance of algorithmic efficiency in real-world applications. In this post, we’ll break down the problem, explore optimal solutions, and equip you with the tools to master it confidently.

Understanding Problem

Determine if it is possible to finish all courses given the prerequisites.

Input

1. numCourses: The total number of courses, numbered from 0 to n-1.
2. prerequisites: A list of pairs [a, b], where course a depends on course b.
   • For example, [2, 1] means you must complete course 1 before you can take course 2.

Output

• Return true if all courses can be completed.
• Return false if it is impossible to complete all courses due to a cyclic dependency.

Challenge

The main challenge lies in detecting cycles in the course dependency graph. A cycle in the graph means there are mutual dependencies between courses, making it impossible to finish all of them.

Key Insights

To approach this problem, you need to recognize that it can be modeled as a directed graph:

• Nodes represent courses.
• Edges represent prerequisites, pointing from course b to course a in the pair [a, b].

The task then reduces to determining whether this directed graph contains a cycle:

• If the graph has a cycle, it is impossible to complete all courses.
• If the graph is acyclic, it is possible to complete all courses.

Approach 1: DFS with Cycle Detection

The brute-force approach revolves around using Depth-First Search (DFS) to determine if all courses can be completed. Here’s how it works:

1. Check Each Course:

• For each course, perform a DFS to verify if it can be completed without creating a cycle in the dependency graph.

2. Cycle Detection:

• Track visited nodes during the DFS traversal to detect cycles.

• If a cycle is detected, it implies that completing all courses is not possible.

3. Recursive Traversal:

• Recursively visit the prerequisites of a course.

• Use a “visited” set to prevent revisiting nodes that are part of the current traversal path.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // Build the graph as an adjacency list
    List<List<Integer>> 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]);
    }
    
    // Check for cycles using DFS
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(graph, i, new boolean[numCourses], new boolean[numCourses])) {
            return false; // Cycle detected
        }
    }
    
    return true; // No cycles found
}

private boolean hasCycle(List<List<Integer>> graph, int course, boolean[] visited, boolean[] path) {
    if (path[course]) {
        return true; // Cycle detected
    }
    if (visited[course]) {
        return false; // Already processed
    }
    
    // Mark this course as visited and part of the current path
    visited[course] = true;
    path[course] = true;
    
    for (int neighbor : graph.get(course)) {
        if (hasCycle(graph, neighbor, visited, path)) {
            return true;
        }
    }
    
    // Backtrack: remove the course from the current path
    path[course] = false;
    return false;
}

Approach 2: Topological Sort (Kahn’s Algorithm)

This approach uses a breadth-first traversal to process nodes (courses) with no prerequisites and checks for cycles in the dependency graph.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // Build the graph 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]]++;
    }
    
    // Queue for courses with no prerequisites
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.add(i);
        }
    }
    
    // Process courses
    int processedCourses = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processedCourses++;
        for (int neighbor : graph.get(course)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.add(neighbor);
            }
        }
    }
    
    return processedCourses == numCourses;
}

Steps

1. Build the Graph:

• Represent the prerequisites as a directed graph using an adjacency list.

• Each course is a node, and a directed edge points from a prerequisite course to its dependent course.

2. Compute In-Degree:

• Calculate the in-degree (number of incoming edges) for each node.

• Nodes with an in-degree of 0 have no prerequisites and can be processed immediately.

3. Process Nodes with No Dependencies:

• Use a queue to store all nodes with an in-degree of 0.

• These nodes can be taken without any prior course completion.

4. Reduce Dependencies:

• Remove the node from the queue, process it, and reduce the in-degree of its neighbors (dependent nodes).

• If a neighbor’s in-degree becomes 0, add it to the queue.

5. Check for Cycles:

• If all nodes are processed, it means there are no cycles, and all courses can be completed. Otherwise, a cycle exists.

Complexity

• Time Complexity: O(V + E)

• Building the graph and computing in-degrees require O(V + E).

• Processing each node and edge takes O(V + E).

• Space Complexity: O(V + E)

• Space is used for the adjacency list and in-degree array.

DFS vs. BFS in Solving Course Schedule Problems: Key Differences and Tradeoffs

1. Memory Usage

• DFS is generally more space-efficient in wide graphs, as it only tracks the recursion stack.

• BFS requires a queue, which can grow large in graphs with many nodes at the same level.

2. Simplicity

• DFS is conceptually simpler for cycle detection but requires careful management of states.

• BFS, while indirect for cycle detection, simplifies the problem by focusing on in-degree calculations.

3. Output Requirements

• Use BFS when the problem requires a topological sort (e.g., Course Schedule II).

• DFS is better suited for problems where the focus is solely on cycle detection.

4. Graph Depth

• DFS is efficient for graphs with limited depth but can fail for excessively deep graphs due to stack overflow.

• BFS handles deep graphs better, provided the graph is not too wide.

Conclusion

The Course Schedule I problem is a fundamental graph problem that challenges us to detect cycles in a directed graph of course dependencies. By understanding and applying DFS with Cycle Detection and BFS using Kahn’s Algorithm, you can tackle this problem efficiently and gain insights into different graph traversal techniques. Each approach has its own strengths and tradeoffs: DFS provides direct cycle detection and is space-efficient for moderately deep graphs, while BFS offers a structured way to achieve a topological sort, making it ideal for problems requiring task order. Mastering these algorithms not only equips you to solve the Course Schedule problem but also prepares you for more advanced graph problems like Course Schedule II, Alien Dictionary, and other real-world dependency resolution scenarios. Whether you choose DFS or BFS, understanding their underlying principles will give you a solid foundation for tackling a wide range of graph-based challenges.