Course Schedule
MedPrompt
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.
- For example, the pair
[0, 1], indicates that to take course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCourses- All the pairs prerequisites[i] are unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses an adjacency matrix to represent the course prerequisites and performs DFS to detect cycles in the graph.
Algorithm
- Create an adjacency matrix from prerequisites
- For each course:
- Perform DFS with visited and recursion stack arrays
- If cycle is detected, return false
- Return true if no cycles found
Walkthrough
In this approach, we first create an adjacency matrix of size numCourses × numCourses to represent the prerequisites. For each prerequisite pair [a, b], we set matrix[a][b] = 1 indicating course b is required for course a. Then we perform DFS starting from each course to detect if there's a cycle in the graph.
class Solution { private boolean dfs(int[][] matrix, boolean[] visited, boolean[] recursionStack, int course) { if (recursionStack[course]) return true; // cycle detected if (visited[course]) return false; visited[course] = true; recursionStack[course] = true; for (int i = 0; i < matrix.length; i++) { if (matrix[course][i] == 1 && dfs(matrix, visited, recursionStack, i)) { return true; } } recursionStack[course] = false; return false; } public boolean canFinish(int numCourses, int[][] prerequisites) { int[][] matrix = new int[numCourses][numCourses]; for (int[] pre : prerequisites) { matrix[pre[0]][pre[1]] = 1; } boolean[] visited = new boolean[numCourses]; boolean[] recursionStack = new boolean[numCourses]; for (int i = 0; i < numCourses; i++) { if (dfs(matrix, visited, recursionStack, i)) { return false; } } return true; }}```Complexity
Time
O(n^2) where n is the number of courses, as we need to traverse the entire matrix
Space
O(n^2) for the adjacency matrix + O(n) for recursion stack
Trade-offs
Pros
Simple to understand and implement
Good for dense graphs
Easy to modify for additional requirements
Cons
High space complexity due to adjacency matrix
Not efficient for sparse graphs
Unnecessary space usage when prerequisites are few
Solutions
Solution
public class Solution { public bool CanFinish(int numCourses, int[][] prerequisites) { var g = new List < int > [numCourses]; for (int i = 0; i < numCourses; ++i) { g[i] = new List < int > (); } var indeg = new int[numCourses]; foreach(var p in prerequisites) { int a = p[0], b = p[1]; g[b].Add(a); ++indeg[a]; } var q = new Queue < int > (); for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { q.Enqueue(i); } } var cnt = 0; while (q.Count > 0) { int i = q.Dequeue(); ++cnt; foreach(int j in g[i]) { if (--indeg[j] == 0) { q.Enqueue(j); } } } return cnt == numCourses; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.