LeetCode Solution 207 - Course Schedule

Problem Statement

You are given numCourses which represents the number of courses you need to take, labeled from 0 to numCourses - 1. You are also given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi before taking course ai.

Return true if you can finish all courses, or false otherwise.

Example 1:

Input:

numCourses = 2, prerequisites = [[1,0]]

Output:

true

Explanation:

You can take course 0 first, then course 1.

Example 2:

Input:

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output:

false

Explanation:

There is a cycle in the prerequisites, making it impossible to finish all courses.

---

Optimal Approach

The problem is about detecting if we can complete all courses based on given prerequisites. This forms a Directed Graph, and the problem reduces to detecting cycles in this graph.

Approach:

• Construct a graph where each course is a node and edges represent prerequisites.
• Use Topological Sorting with Kahn’s Algorithm (BFS) or DFS with cycle detection.
• If there is a cycle, return false.
• If we can traverse all courses without cycles, return true.

---

C++ Code Implementations

BFS (Kahn's Algorithm - Topological Sorting)

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        for (auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }
        
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        int count = 0;
        while (!q.empty()) {
            int course = q.front(); q.pop();
            count++;
            for (int next : graph[course]) {
                if (--inDegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return count == numCourses;
    }
};

DFS (Cycle Detection)

class Solution {
public:
    bool dfs(int course, vector<vector<int>>& graph, vector<int>& visited) {
        if (visited[course] == 1) return false; // Cycle detected
        if (visited[course] == 2) return true;  // Already processed
        
        visited[course] = 1; // Mark as processing
        for (int next : graph[course]) {
            if (!dfs(next, graph, visited)) return false;
        }
        visited[course] = 2; // Mark as processed
        return true;
    }
    
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }
        vector<int> visited(numCourses, 0);
        
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, graph, visited)) return false;
        }
        return true;
    }
};

---

Step-by-Step Explanation

1. Graph Construction:

   • Convert prerequisites into an adjacency list representation.
   • Compute inDegree (BFS) or use a visited array (DFS) for cycle detection.

2. Cycle Detection:

   • BFS (Kahn's Algorithm):
     • Start with nodes having inDegree = 0.
     • Remove nodes one by one while updating inDegree of neighbors.
     • If we process all nodes, return true; otherwise, false.
   • DFS:
     • Use a visited array where:
       • 0 = Unvisited
       • 1 = Processing
       • 2 = Processed
     • If a node is visited again while processing, it means there’s a cycle.

---

Dry Run Example

Input:

numCourses = 3, prerequisites = [[1,0],[2,1]]

BFS Execution:

1. Graph: {0 -> [1], 1 -> [2]}
2. In-degree: [0, 1, 1]
3. Start with 0 → Process 1 → Process 2
4. All nodes processed → Return true

DFS Execution:

1. Call DFS on 0 → Visit 1 → Visit 2
2. No cycles found → Return true

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Checking all paths)	O(V!)	O(V)	Too slow for large inputs
DFS with visited array	O(V + E)	O(V)	Efficient, but harder to implement than BFS
BFS (Kahn’s Algorithm)	O(V + E)	O(V)	Best approach for this problem

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
BFS (Kahn’s Algorithm)	O(V + E)	O(V + E)
DFS (Cycle Detection)	O(V + E)	O(V + E)

---

Conclusion

• The best approach is Topological Sorting using BFS (Kahn's Algorithm) as it efficiently detects cycles and determines a valid order.
• DFS is another good approach but requires cycle detection logic.
• Similar problems to practice:
  • Course Schedule II (LeetCode 210)
  • Alien Dictionary
  • Detect Cycle in Directed Graph

Happy coding! 🚀