Course Schedule Solution & Editorial - DSA Pattern

Course Schedule Solution & Editorial - DSA Pattern | Thita.ai

cpp
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // Build Adjacency List
        vector<vector<int>> adj(numCourses);
        for (const auto& edge : prerequisites) {
            adj[edge[1]].push_back(edge[0]);
        }

        // States: 0 = Unvisited, 1 = Visiting, 2 = Visited
        vector<int> state(numCourses, 0);

        for (int i = 0; i < numCourses; ++i) {
            if (state[i] == 0) {
                if (hasCycle(i, adj, state)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool hasCycle(int node, const vector<vector<int>>& adj, vector<int>& state) {
        state[node] = 1; // Mark as Visiting (in recursion stack)

        for (int neighbor : adj[node]) {
            if (state[neighbor] == 1) {
                return true; // Cycle detected: back edge to a node in stack
            }
            if (state[neighbor] == 0) {
                if (hasCycle(neighbor, adj, state)) {
                    return true;
                }
            }
        }

        state[node] = 2; // Mark as Visited (fully processed)
        return false;
    }
};

java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build Adjacency List
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : prerequisites) {
            adj.get(edge[1]).add(edge[0]);
        }

        // States: 0 = Unvisited, 1 = Visiting, 2 = Visited
        int[] state = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                if (hasCycle(i, adj, state)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
        state[node] = 1; // Mark as Visiting

        for (int neighbor : adj.get(node)) {
            if (state[neighbor] == 1) {
                return true; // Cycle detected
            }
            if (state[neighbor] == 0) {
                if (hasCycle(neighbor, adj, state)) {
                    return true;
                }
            }
        }

        state[node] = 2; // Mark as Visited
        return false;
    }
}

python
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build Adjacency List
        adj = [[] for _ in range(numCourses)]
        for dest, src in prerequisites:
            adj[src].append(dest)
        
        # States: 0 = Unvisited, 1 = Visiting, 2 = Visited
        state = [0] * numCourses
        
        def has_cycle(node):
            state[node] = 1 # Mark as Visiting
            
            for neighbor in adj[node]:
                if state[neighbor] == 1:
                    return True # Cycle detected
                if state[neighbor] == 0:
                    if has_cycle(neighbor):
                        return True
            
            state[node] = 2 # Mark as Visited
            return False

        for i in range(numCourses):
            if state[i] == 0:
                if has_cycle(i):
                    return False
                    
        return True

AI Coach Insight

Focus on the core pattern. For Course Schedule, identifying the Graph Traversal Patterns (DFS & BFS) is key to optimizing your solution.

Complexity Analysis

Time Complexity: $O(V + E)$

$V$ is numCourses and $E$ is the length of prerequisites.
We build the graph in $O(E)$ .
In the DFS, each node is visited and processed exactly once (transitioning from Unvisited to Visiting to Visited).
Each edge is inspected exactly once.

Space Complexity: $O(V + E)$

Adjacency list takes $O(V + E)$ .
The recursion stack can go up to $O(V)$ in the worst case (a long line of dependencies).
The state array takes $O(V)$ .

Related Patterns

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.

Common Mistakes & FAQ

Why do I get Time Limit Exceeded (TLE) with a simple boolean visited array?
- The Mistake: Using only two states (Visited vs Not Visited) and resetting the visited status after backtracking (like in pathfinding).
- Conceptual Gap: This turns the algorithm into a brute force path search. You re-process the same subgraphs multiple times.
- Consequence: Exponential time complexity. You must use the third state ("Visited/Processed") to memoize safe nodes.
Why is my solution failing on disconnected graphs?
- The Mistake: Only running DFS from node 0.
- Conceptual Gap: The graph might be a forest (multiple disconnected components). Node 0 might not have a path to the component containing the cycle.
- Consequence: The algorithm returns true (can finish) even when a cycle exists in a disconnected component. You must loop through 0 to .

numCourses - 1

Editorial: Course Schedule

LeetCode 207: Course Schedule Solution & Explanation

Problem Overview

Brute Force Approach for Course Schedule

Want to master more patterns?

Core Insight for Course Schedule

Execution Flow

Proof of Correctness

Reference Implementation

C++ Solution for LeetCode 207

Java Solution for LeetCode 207

Python Solution for LeetCode 207

AI Coach Insight

Complexity Analysis

Related Patterns

Common Mistakes & FAQ