Course Schedule

LeetCode 207: Course Schedule Solution & Explanation

Problem Overview

TL;DR: To solve LeetCode 207, model the courses as a directed graph and use Depth-First Search (DFS) to detect if a cycle exists; if a cycle is found, it is impossible to finish all courses.

The Course Schedule problem asks whether it is possible to complete a specific number of courses given a list of prerequisites. Each prerequisite is a dependency: to take course A, you must first complete course B. This relationship forms a directed edge from B to A. If a set of courses forms a circular dependency (e.g., A depends on B, B depends on A), it is impossible to complete them. This is a classic "deadlock" detection problem.

Brute Force Approach for Course Schedule

A naive brute force approach attempts to simulate taking courses by checking every possible path for loops. For each course, we could initiate a traversal to see if we eventually return to the starting course.

Pseudo-code:

For each course i from 0 to numCourses - 1:
    Start a DFS from i
    If the DFS path encounters i again:
        Return False (Cycle detected)
Return True

Why it fails: The time complexity of this approach is inefficient. Without memorizing which nodes have already been fully processed and verified to be cycle-free, the algorithm effectively re-traverses large portions of the graph repeatedly.

• Time Complexity: $O(V \cdot (V + E))$, where $V$ is the number of courses and $E$ is the number of prerequisites. In a dense graph, this can approach $O(V^3)$.
• Result: This often leads to a Time Limit Exceeded (TLE) on larger inputs because we do not cache the results of previous traversals.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We will implement the optimal solution using the Graph DFS - Cycle Detection strategy.

1. Graph Construction: Convert the input prerequisites edge list into an Adjacency List. This allows for $O(1)$ access to neighbors.
2. State Array: Initialize an array state of size numCourses with all values set to 0 (Unvisited).
3. Iterate All Nodes: Since the graph might be disconnected (forest of graphs), we must iterate through every course from 0 to n-1.
   • If a node is Unvisited, launch a DFS from it.
   • If the DFS returns false (cycle detected), strictly return false.
4. DFS Function:
   • Mark current node as Visiting (1).
   • Iterate through all neighbors:
     • If neighbor is Visiting (1): Cycle detected. Return true (cycle exists).
     • If neighbor is Unvisited (0): Recursively call DFS. If the recursive call finds a cycle, propagate that up.
     • If neighbor is Visited (2): Skip it.
   • After processing all neighbors, mark current node as Visited (2).
   • Return false (no cycle found in this path).

Execution Flow

Let's trace the execution with numCourses = 2 and prerequisites = [[1,0], [0,1]] (Cycle 0 <-> 1).

1. Build Graph: 0 -> [1], 1 -> [0].
2. Main Loop: Start at node 0. State is Unvisited. Call dfs(0).
3. DFS(0):
   • Mark 0 as Visiting.
   • Check neighbors of 0: Neighbor is 1.
   • 1 is Unvisited. Call dfs(1).
4. DFS(1):
   • Mark 1 as Visiting.
   • Check neighbors of 1: Neighbor is 0.
   • CRITICAL CHECK: Node 0 is currently Visiting.
   • This implies a back edge 1 -> 0 while 0 is in the recursion stack.
   • Cycle detected. Return true.
5. Result: The main loop receives the cycle signal and returns false for the problem.

Proof of Correctness

The algorithm relies on the properties of Depth-First Search on directed graphs. The "Three-Color" (or three-state) method is mathematically proven to detect cycles.

• If the graph is a DAG (Directed Acyclic Graph), a topological sort exists, and we will mark all nodes as Visited (2) without ever encountering a Visiting (1) node.
• If there is a cycle, the DFS path must eventually follow an edge pointing to a node that is an ancestor in the current DFS tree. By definition, all ancestors in the current path are marked Visiting. Therefore, the condition state[neighbor] == Visiting is necessary and sufficient to detect a cycle.

Pattern Reuse Notes

The "Graph DFS - Cycle Detection" pattern is highly reusable. Understanding the 3-state coloring logic is crucial for solving these related problems:

• LeetCode 210: Course Schedule II: Identical to Course Schedule, but requires returning the actual topological ordering instead of a boolean.
• LeetCode 802: Find Eventual Safe States: Uses the exact same cycle detection logic; nodes that are not part of any cycle (and don't lead to one) are "safe."
• LeetCode 1059: All Paths from Source Lead to Destination: Requires detecting cycles to ensure paths are finite, combined with sink node verification.

Reference Implementation

C++ Solution for LeetCode 207

1class Solution {
2public:
3    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
4        // Build Adjacency List
5        vector<vector<int>> adj(numCourses);
6        for (const auto& edge : prerequisites) {
7            adj[edge[1]].push_back(edge[0]);
8        }
9
10        // States: 0 = Unvisited, 1 = Visiting, 2 = Visited
11        vector<int> state(numCourses, 0);
12
13        for (int i = 0; i < numCourses; ++i) {
14            if (state[i] == 0) {
15                if (hasCycle(i, adj, state)) {
16                    return false;
17                }
18            }
19        }
20        return true;
21    }
22
23private:
24    bool hasCycle(int node, const vector<vector<int>>& adj, vector<int>& state) {
25        state[node] = 1; // Mark as Visiting (in recursion stack)
26
27        for (int neighbor : adj[node]) {
28            if (state[neighbor] == 1) {
29                return true; // Cycle detected: back edge to a node in stack
30            }
31            if (state[neighbor] == 0) {
32                if (hasCycle(neighbor, adj, state)) {
33                    return true;
34                }
35            }
36        }
37
38        state[node] = 2; // Mark as Visited (fully processed)
39        return false;
40    }
41};

Java Solution for LeetCode 207

1class Solution {
2    public boolean canFinish(int numCourses, int[][] prerequisites) {
3        // Build Adjacency List
4        List<List<Integer>> adj = new ArrayList<>();
5        for (int i = 0; i < numCourses; i++) {
6            adj.add(new ArrayList<>());
7        }
8        for (int[] edge : prerequisites) {
9            adj.get(edge[1]).add(edge[0]);
10        }
11
12        // States: 0 = Unvisited, 1 = Visiting, 2 = Visited
13        int[] state = new int[numCourses];
14
15        for (int i = 0; i < numCourses; i++) {
16            if (state[i] == 0) {
17                if (hasCycle(i, adj, state)) {
18                    return false;
19                }
20            }
21        }
22        return true;
23    }
24
25    private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
26        state[node] = 1; // Mark as Visiting
27
28        for (int neighbor : adj.get(node)) {
29            if (state[neighbor] == 1) {
30                return true; // Cycle detected
31            }
32            if (state[neighbor] == 0) {
33                if (hasCycle(neighbor, adj, state)) {
34                    return true;
35                }
36            }
37        }
38
39        state[node] = 2; // Mark as Visited
40        return false;
41    }
42}

Python Solution for LeetCode 207

1class Solution:
2    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3        # Build Adjacency List
4        adj = [[] for _ in range(numCourses)]
5        for dest, src in prerequisites:
6            adj[src].append(dest)
7        
8        # States: 0 = Unvisited, 1 = Visiting, 2 = Visited
9        state = [0] * numCourses
10        
11        def has_cycle(node):
12            state[node] = 1 # Mark as Visiting
13            
14            for neighbor in adj[node]:
15                if state[neighbor] == 1:
16                    return True # Cycle detected
17                if state[neighbor] == 0:
18                    if has_cycle(neighbor):
19                        return True
20            
21            state[node] = 2 # Mark as Visited
22            return False
23
24        for i in range(numCourses):
25            if state[i] == 0:
26                if has_cycle(i):
27                    return False
28                    
29        return True