Course Schedule
Problem
Given the total number of courses and a list of prerequisite pairs, determine if it is possible to finish all courses by taking them in an order that satisfies all prerequisites.
- 1 ≤ numCourses ≤ 10⁵
- 0 ≤ prerequisites.length ≤ 5000
- prerequisites[i].length == 2
- 0 ≤ a_i, b_i < numCourses
- All the pairs prerequisites[i] are unique.
Example
numCourses = 2, prerequisites = [[1,0]]trueThere are two courses: 0 and 1. To take course 1, you must first take course 0. The order [0,1] satisfies the prerequisites, so it is possible to finish all courses.
Approach
Straightforward Solution
A brute-force approach might try all permutations of courses to check if prerequisites are satisfied, which is factorial in complexity and infeasible for large inputs.
Core Observation
The problem reduces to detecting if a directed graph (courses as nodes, prerequisites as edges) contains a cycle. If a cycle exists, it is impossible to complete all courses because some courses depend on each other circularly.
Path to Optimal
Recognizing the problem as cycle detection in a directed graph leads to using DFS with a recursion stack (visit set) to detect back edges indicating cycles. Constructing an adjacency list from prerequisites allows efficient traversal. The DFS explores each course's prerequisites recursively, marking nodes in the current path. If a node is revisited in the current path, a cycle is detected. Memoization by clearing prerequisites after processing prevents redundant work.
Optimal Approach
Build an adjacency list mapping each course to its prerequisites. For each course, perform a DFS to check for cycles by tracking nodes in the current recursion stack. If a cycle is found, return false immediately. If no cycles are detected after processing all courses, return true. Clearing the prerequisites list after processing a course marks it as safe and avoids repeated DFS calls.
Time
O(V + E)
Each course (vertex) is visited once, and each prerequisite (edge) is explored once during DFS. Memoization by clearing prerequisites ensures no repeated work, resulting in linear time relative to the graph size.
Space
O(V + E)
The adjacency list stores all edges, requiring O(E) space. The recursion stack and visit set use O(V) space in the worst case, where V is the number of courses.
Pattern Spotlight
DFS (Cycle Detection in Directed Graph)
Use a recursion stack (visit set) to detect cycles by tracking nodes currently in the path; revisiting a node in this stack signals a cycle, enabling early termination.
Solution
| 1 | class Solution:
|
| 2 | def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
|
| 3 | pre_map = {i: [] for i in range(numCourses)}
|
| 4 | for crs, pre in prerequisites:
|
| 5 | pre_map[crs].append(pre)
|
| 6 |
|
| 7 | visit_set = set()
|
| 8 | def dfs(crs):
|
| 9 | if crs in visit_set:
|
| 10 | return False
|
| 11 | if pre_map[crs] == []:
|
| 12 | return True
|
| 13 |
|
| 14 | visit_set.add(crs)
|
| 15 | for pre in pre_map[crs]:
|
| 16 | if not dfs(pre): return False
|
| 17 | visit_set.remove(crs)
|
| 18 | pre_map[crs] = []
|
| 19 | return True
|
| 20 |
|
| 21 | for crs in range(numCourses):
|
| 22 | if not dfs(crs): return False
|
| 23 | return True |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean canFinish(int numCourses, int[][] prerequisites) { |
| 5 | Map<Integer, List<Integer>> preMap = new HashMap<>(); |
| 6 | for (int i = 0; i < numCourses; i++) { |
| 7 | preMap.put(i, new ArrayList<>()); |
| 8 | } |
| 9 | for (int[] pair : prerequisites) { |
| 10 | preMap.get(pair[0]).add(pair[1]); |
| 11 | } |
| 12 | |
| 13 | Set<Integer> visitSet = new HashSet<>(); |
| 14 | |
| 15 | // DFS function as a lambda is not straightforward in Java 8-, so use a helper method |
| 16 | // We'll define a private helper method dfs below |
| 17 | for (int crs = 0; crs < numCourses; crs++) { |
| 18 | if (!dfs(crs, preMap, visitSet)) { |
| 19 | return false; |
| 20 | } |
| 21 | } |
| 22 | return true; |
| 23 | } |
| 24 | |
| 25 | private boolean dfs(int crs, Map<Integer, List<Integer>> preMap, Set<Integer> visitSet) { |
| 26 | if (visitSet.contains(crs)) { |
| 27 | return false; |
| 28 | } |
| 29 | if (preMap.get(crs).isEmpty()) { |
| 30 | return true; |
| 31 | } |
| 32 | |
| 33 | visitSet.add(crs); |
| 34 | for (int pre : preMap.get(crs)) { |
| 35 | if (!dfs(pre, preMap, visitSet)) { |
| 36 | return false; |
| 37 | } |
| 38 | } |
| 39 | visitSet.remove(crs); |
| 40 | preMap.put(crs, new ArrayList<>()); |
| 41 | return true; |
| 42 | } |
| 43 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <unordered_set> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { |
| 10 | unordered_map<int, vector<int>> preMap; |
| 11 | for (int i = 0; i < numCourses; ++i) { |
| 12 | preMap[i] = vector<int>(); |
| 13 | } |
| 14 | for (const auto& pair : prerequisites) { |
| 15 | preMap[pair[0]].push_back(pair[1]); |
| 16 | } |
| 17 | |
| 18 | unordered_set<int> visitSet; |
| 19 | |
| 20 | for (int crs = 0; crs < numCourses; ++crs) { |
| 21 | if (!dfs(crs, preMap, visitSet)) { |
| 22 | return false; |
| 23 | } |
| 24 | } |
| 25 | return true; |
| 26 | } |
| 27 | |
| 28 | private: |
| 29 | bool dfs(int crs, unordered_map<int, vector<int>>& preMap, unordered_set<int>& visitSet) { |
| 30 | if (visitSet.count(crs)) { |
| 31 | return false; |
| 32 | } |
| 33 | if (preMap[crs].empty()) { |
| 34 | return true; |
| 35 | } |
| 36 | |
| 37 | visitSet.insert(crs); |
| 38 | for (int pre : preMap[crs]) { |
| 39 | if (!dfs(pre, preMap, visitSet)) { |
| 40 | return false; |
| 41 | } |
| 42 | } |
| 43 | visitSet.erase(crs); |
| 44 | preMap[crs].clear(); |
| 45 | return true; |
| 46 | } |
| 47 | }; |
| 1 | var canFinish = function(numCourses, prerequisites) { |
| 2 | const preMap = new Map(); |
| 3 | for (let i = 0; i < numCourses; i++) { |
| 4 | preMap.set(i, []); |
| 5 | } |
| 6 | for (const [crs, pre] of prerequisites) { |
| 7 | preMap.get(crs).push(pre); |
| 8 | } |
| 9 | |
| 10 | const visitSet = new Set(); |
| 11 | |
| 12 | function dfs(crs) { |
| 13 | if (visitSet.has(crs)) { |
| 14 | return false; |
| 15 | } |
| 16 | if (preMap.get(crs).length === 0) { |
| 17 | return true; |
| 18 | } |
| 19 | |
| 20 | visitSet.add(crs); |
| 21 | for (const pre of preMap.get(crs)) { |
| 22 | if (!dfs(pre)) { |
| 23 | return false; |
| 24 | } |
| 25 | } |
| 26 | visitSet.delete(crs); |
| 27 | preMap.set(crs, []); |
| 28 | return true; |
| 29 | } |
| 30 | |
| 31 | for (let crs = 0; crs < numCourses; crs++) { |
| 32 | if (!dfs(crs)) { |
| 33 | return false; |
| 34 | } |
| 35 | } |
| 36 | return true; |
| 37 | }; |
Step-by-Step Solution
Build Adjacency List Mapping Courses to Prerequisites
| 3 | pre_map = {i: [] for i in range(numCourses)}
|
| 4 | for crs, pre in prerequisites:
|
| 5 | pre_map[crs].append(pre)
|
Objective
To represent the course prerequisites as a graph for efficient traversal.
Key Insight
An adjacency list is a natural and efficient way to represent directed graphs, especially when edges are sparse. Mapping each course to its list of prerequisites allows quick access to dependencies during DFS. This structure transforms the problem into graph traversal and cycle detection.
Interview Quick-Check
Core Logic
The adjacency list stores all prerequisite edges, enabling O(1) access to a course's prerequisites during DFS.
Common Pitfalls & Bugs
Forgetting to initialize all courses in the adjacency list can cause key errors or missed nodes during traversal.
Use DFS with Recursion Stack to Detect Cycles
| 7 | visit_set = set()
|
| 8 | def dfs(crs):
|
| 9 | if crs in visit_set:
|
| 10 | return False
|
| 11 | if pre_map[crs] == []:
|
| 12 | return True
|
| 14 | visit_set.add(crs)
|
| 15 | for pre in pre_map[crs]:
|
| 16 | if not dfs(pre): return False
|
| 17 | visit_set.remove(crs)
|
| 18 | pre_map[crs] = []
|
| 19 | return True
|
Objective
To recursively explore prerequisites and detect cycles by tracking the current path.
Key Insight
DFS explores each course's prerequisites depth-first. The recursion stack (visit_set) tracks nodes currently being explored. If a node is encountered that is already in this stack, it indicates a cycle. Clearing the prerequisites list after processing a course marks it as safe, preventing redundant DFS calls and improving efficiency.
Interview Quick-Check
Core Logic
The recursion stack detects cycles by identifying back edges, and memoization by clearing prerequisites avoids repeated work.
State & Boundaries
Base cases: returning False immediately on cycle detection, and True when a course has no prerequisites left.
Common Pitfalls & Bugs
Failing to remove a course from the recursion stack after DFS exploration leads to false cycle detection or infinite recursion.
Iterate Over All Courses to Verify Completion Feasibility
| 21 | for crs in range(numCourses):
|
| 22 | if not dfs(crs): return False
|
| 23 | return True |
Objective
To ensure all courses are checked for cycles and dependencies.
Key Insight
Since the graph may be disconnected, each course must be checked. If any DFS call detects a cycle, the function returns False immediately. If all courses are processed without cycles, the function returns True, confirming all courses can be completed.
Interview Quick-Check
Core Logic
Iterating over all courses guarantees that disconnected components and isolated nodes are also checked for cycles.
Complexity
Early termination on cycle detection improves average runtime by avoiding unnecessary DFS calls.
Line Analysis
This solution has 9 Critical lines interviewers watch for.
if crs in visit_set:Check if the current course is already in the recursion stack.
Detecting a course in the current path signals a cycle, which invalidates the course completion order.
visit_set.remove(crs)Remove the current course from the recursion stack after exploration.
Removing the course restores state for other DFS paths and prevents false cycle detection in separate branches.
visit_set = set()Initialize a set to track courses currently in the recursion stack.
The visit_set tracks the current DFS path to detect cycles by identifying back edges, which is critical for correctness.
return FalseReturn False immediately upon cycle detection.
Early termination on cycle detection prevents unnecessary further exploration and correctly signals impossibility.
visit_set.add(crs)Add the current course to the recursion stack.
Marking the course as being explored enables cycle detection by tracking the current DFS path.
for pre in pre_map[crs]:Recursively DFS on each prerequisite of the current course.
Exploring all prerequisites ensures that dependencies are validated and cycles are detected in the entire prerequisite chain.
if not dfs(pre): return FalseReturn False immediately if any prerequisite DFS detects a cycle.
Propagating cycle detection up the recursion stack ensures the entire function returns False if any cycle exists.
pre_map[crs] = []Clear the prerequisites list for the current course to memoize safe completion.
Memoization by clearing prerequisites marks the course as processed and safe, avoiding redundant DFS calls and improving efficiency.
if not dfs(crs): return FalseReturn False immediately if DFS detects a cycle for any course.
Early termination on cycle detection prevents unnecessary checks and correctly signals impossibility to complete all courses.
pre_map = {i: [] for i in range(numCourses)}Initialize adjacency list mapping each course to an empty list of prerequisites.
Creating a complete adjacency list upfront ensures every course is represented, preventing key errors and enabling uniform graph traversal.
pre_map[crs].append(pre)Append the prerequisite course to the current course's adjacency list.
Adding edges to the adjacency list encodes the prerequisite relationship, which is essential for detecting cycles and ordering courses.
if pre_map[crs] == []:Check if the current course has no prerequisites left.
A course with no prerequisites is safe to complete, serving as a base case for recursion.
return TrueReturn True indicating the current course can be completed safely.
Returning True signals successful DFS traversal without cycles for this course and its prerequisites.
for crs in range(numCourses):Iterate over all courses to check for cycles and completion feasibility.
Checking every course ensures disconnected components and isolated nodes are validated, guaranteeing correctness.
return TrueReturn True if all courses can be completed without cycles.
Returning True confirms that the entire course graph is acyclic and all courses can be finished in some order.
for crs, pre in prerequisites:Iterate over each prerequisite pair to populate the adjacency list.
This loop builds the graph edges by associating each course with its prerequisites, forming the dependency structure needed for DFS.
return TrueReturn True when no prerequisites remain, indicating safe completion.
This base case terminates recursion successfully when a course is free of dependencies.
def dfs(crs):Define the DFS function to explore prerequisites of a given course.
Encapsulating the recursive logic in a helper function organizes the cycle detection process and manages state cleanly.
Test Your Understanding
Why does detecting a node already in the recursion stack during DFS indicate a cycle?
Because revisiting a node in the current recursion path means there is a back edge, forming a cycle where a course depends on itself indirectly, making it impossible to complete.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Course Schedule from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Course Schedule drill