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
This approach uses an adjacency list representation and performs DFS to detect cycles in the graph, which is more space-efficient for sparse graphs.
Algorithm
- Create an adjacency list 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
We create an adjacency list representation using a List<List<Integer>> where for each course, we store a list of its prerequisites. Then we perform DFS to detect cycles.
class Solution { private boolean hasCycle(List<List<Integer>> adj, boolean[] visited, boolean[] recursionStack, int course) { if (recursionStack[course]) return true; if (visited[course]) return false; visited[course] = true; recursionStack[course] = true; for (int neighbor : adj.get(course)) { if (hasCycle(adj, visited, recursionStack, neighbor)) { return true; } } recursionStack[course] = false; return false; } public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { adj.add(new ArrayList<>()); } for (int[] pre : prerequisites) { adj.get(pre[0]).add(pre[1]); } boolean[] visited = new boolean[numCourses]; boolean[] recursionStack = new boolean[numCourses]; for (int i = 0; i < numCourses; i++) { if (hasCycle(adj, visited, recursionStack, i)) { return false; } } return true; }}```Complexity
Time
O(V + E) where V is number of courses and E is number of prerequisites
Space
O(V + E) for adjacency list + O(V) for recursion stack
Trade-offs
Pros
More space-efficient for sparse graphs
Better time complexity for sparse graphs
Memory usage proportional to number of prerequisites
Cons
Slightly more complex implementation
Not as efficient for dense graphs
Recursive calls can lead to stack overflow for very large graphs
This approach uses Kahn's algorithm for topological sorting, which is an iterative approach using indegree of vertices to detect cycles.
Algorithm
- Calculate indegree for each course
- Add courses with indegree 0 to queue
- While queue is not empty:
- Remove a course and increment count
- Reduce indegree of dependent courses
- Add new courses with indegree 0 to queue
- Return true if count equals total courses
Walkthrough
We use Kahn's algorithm which works by keeping track of courses with no prerequisites (indegree = 0) and removing them one by one, reducing the indegree of their dependent courses. If we can process all courses, there's no cycle.
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int[] indegree = new int[numCourses]; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { adj.add(new ArrayList<>()); } // Build adjacency list and calculate indegree for (int[] pre : prerequisites) { adj.get(pre[1]).add(pre[0]); indegree[pre[0]]++; } Queue<Integer> queue = new LinkedList<>(); // Add all courses with no prerequisites to queue for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) queue.offer(i); } int count = 0; while (!queue.isEmpty()) { int course = queue.poll(); count++; for (int neighbor : adj.get(course)) { indegree[neighbor]--; if (indegree[neighbor] == 0) { queue.offer(neighbor); } } } return count == numCourses; }}```Complexity
Time
O(V + E) where V is number of courses and E is number of prerequisites
Space
O(V + E) for adjacency list and queue
Trade-offs
Pros
Non-recursive solution avoiding stack overflow
Efficient for both sparse and dense graphs
Can easily be modified to return the order of courses
More intuitive for course scheduling context
Cons
Requires additional space for queue and indegree array
May not be as intuitive for those unfamiliar with topological sort
Cannot provide cycle path if one exists
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; }}public class Course_Schedule { public class Solution_bfs { public boolean canFinish ( int numCourses , int [][] prerequisites ) { // Kahn's Algorithm if ( numCourses <= 0 ) { return false ; } if ( prerequisites == null || prerequisites . length == 0 ) { return true ; } int [] inDegree = new int [ numCourses ]; // 1. setup indgree count for ( int [] edge : prerequisites ) { inDegree [ edge [ 0 ]]++; } Queue < Integer > queue = new LinkedList <>(); // 2. start from node with no indgree, i.e. no prerquisites for this course for ( int i = 0 ; i < inDegree . length ; i ++) { if ( inDegree [ i ] == 0 ) { queue . offer ( i ); } } List < Integer > result = new ArrayList <>(); while (! queue . isEmpty ()) { int currentCourse = queue . poll (); result . add ( currentCourse ); for ( int [] edge : prerequisites ) { if ( edge [ 1 ] == currentCourse ) { // if a course requires current course if (-- inDegree [ edge [ 0 ]] == 0 ) // -1, since current course is taken, and fulfill course edge[0] queue . offer ( edge [ 0 ]); } } } return result . size () == numCourses ; } } public class Solution_dfs { public boolean canFinish ( int numCourses , int [][] prerequisites ) { if ( prerequisites == null || prerequisites . length < 2 ) { return true ; } // 0 for not visited，1 for globally visited，-1 for visisted AND on current path int [] isVisited = new int [ numCourses ]; List < List < Integer >> graph = new ArrayList <>(); // 1. build graph for ( int i = 0 ; i < numCourses ; i ++) { graph . add ( new ArrayList <>()); } for ( int [] each: prerequisites ) { graph . get ( each [ 1 ]). add ( each [ 0 ]); } // 2. dfs for ( int i = 0 ; i < numCourses ; i ++) { if (! dfs ( i , isVisited , graph )) { return false ; } } return true ; } private boolean dfs ( int courseIndex , int [] isVisited , List < List < Integer >> graph ) { if ( isVisited [ courseIndex ] == 1 ) { return true ; } if ( isVisited [ courseIndex ] == - 1 ) { return false ; // cycle found } isVisited [ courseIndex ] = - 1 ; for ( Integer next: graph . get ( courseIndex )) { if (! dfs ( next , isVisited , graph )) { return false ; } } isVisited [ courseIndex ] = 1 ; return true ; } } } ////// class Solution { public boolean canFinish ( int numCourses , int [][] prerequisites ) { List < Integer >[] g = new List [ numCourses ]; Arrays . setAll ( g , k -> new ArrayList <>()); int [] indeg = new int [ numCourses ]; for ( var p : prerequisites ) { int a = p [ 0 ], b = p [ 1 ]; g [ b ]. add ( a ); ++ indeg [ a ]; } Deque < Integer > q = new ArrayDeque <>(); for ( int i = 0 ; i < numCourses ; ++ i ) { if ( indeg [ i ] == 0 ) { q . offer ( i ); } } int cnt = 0 ; while (! q . isEmpty ()) { int i = q . poll (); ++ cnt ; for ( int j : g [ i ]) { if (-- indeg [ j ] == 0 ) { q . offer ( j ); } } } return cnt == numCourses ; } }class Solution {public: bool canFinish(int numCourses, vector<vector<int>> &prerequisites) { vector<vector<int>> g(numCourses); vector<int> indeg(numCourses); for (auto &p : prerequisites) { int a = p[0], b = p[1]; g[b].push_back(a); ++indeg[a]; } queue<int> q; for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { q.push(i); } } int cnt = 0; while (!q.empty()) { int i = q.front(); q.pop(); ++cnt; for (int j : g[i]) { if (--indeg[j] == 0) { q.push(j); } } } return cnt == numCourses; }};''' >>> from collections import defaultdict >>> a = defaultdict(int) >>> a defaultdict(<type 'int'>, {}) >>> >>> a['hehehe'] 0 >>> a defaultdict(<type 'int'>, {'hehehe': 0}) >>> a = defaultdict(list) >>> a defaultdict(<type 'list'>, {}) >>> a['hehehe'] [] >>> a defaultdict(<type 'list'>, {'hehehe': []}) ''' class Solution : def canFinish ( self , numCourses : int , prerequisites : List [ List [ int ]]) -> bool : g = defaultdict ( list ) indeg = [ 0 ] * numCourses for a , b in prerequisites : g [ b ]. append ( a ) indeg [ a ] += 1 cnt = 0 q = deque ([ i for i , v in enumerate ( indeg ) if v == 0 ]) while q : i = q . popleft () cnt += 1 for j in g [ i ]: indeg [ j ] -= 1 if indeg [ j ] == 0 : q . append ( j ) return cnt == numCoursesVideo 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.