Course Schedule
Problem Statement
You are given an array prerequisites
where prerequisites[i] = [a, b]
indicates that you must take course b
first if you want to take course a
.
The pair [0, 1]
, indicates that must take course 1
before taking course 0
.
There are a total of numCourses
courses you are required to take, labeled from 0
to numCourses - 1
.
Return true
if it is possible to finish all courses, otherwise return false
.
Example 1:
Input: numCourses = 2, prerequisites = [[0,1]]
Output: true
Explanation: First take course 1 (no prerequisites) and then take course 0.
Example 2:
Input: numCourses = 2, prerequisites = [[0,1],[1,0]]
Output: false
Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.
Constraints:
1 <= numCourses <= 1000
0 <= prerequisites.length <= 1000
- All
prerequisite
pairs are unique.
You should aim for a solution with O(V + E)
time and O(V + E)
space, where V
is the number of courses (nodes) and E
is the number of prerequisites (edges).
Recommended Time and Space Complexity
You should aim for a solution with O(V + E)
time and O(V + E)
space, where V
is the number of courses (nodes) and E
is the number of prerequisites (edges).
Hint 1
Consider the problem as a graph where courses represent the nodes, and prerequisite[i] = [a, b]
represents a directed edge from a
to b
. We need to determine whether the graph contains a cycle. Why? Because if there is a cycle, it is impossible to complete the courses involved in the cycle. Can you think of an algorithm to detect cycle in a graph?
Hint 2
We can use the Depth First Search (DFS) algorithm to detect a cycle in a graph. We iterate over each course, run a DFS from that course, and first try to finish its prerequisite courses by recursively traversing through them. To detect a cycle, we initialize a hash set called path
, which contains the nodes visited in the current DFS call. If we encounter a course that is already in the path
, we can conclude that a cycle is detected. How would you implement it?
Hint 3
We run a DFS starting from each course by initializing a hash set, path
, to track the nodes in the current DFS call. At each step of the DFS, we return false
if the current node is already in the path
, indicating a cycle. We recursively traverse the neighbors of the current node, and if any of the neighbor DFS calls detect a cycle, we immediately return false
. Additionally, we clear the neighbors list of a node when no cycle is found from that node to avoid revisiting those paths again.
Solution
Cycle Detection (DFS)
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool: """ Determines if it is possible to finish all courses given the prerequisites.
Args: num_courses: The total number of courses. prerequisites: A list of prerequisite pairs, where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.
Returns: True if it is possible to finish all courses, otherwise False. """ # Map each course to its prerequisites pre_map = {i: [] for i in range(num_courses)} for crs, pre in prerequisites: pre_map[crs].append(pre)
# Store all courses along the current DFS path visiting = set()
def dfs(crs): if crs in visiting: # Cycle detected return False if not pre_map[crs]: return True
visiting.add(crs) for pre in pre_map[crs]: if not dfs(pre): return False visiting.remove(crs) pre_map[crs] = [] return True
for c in range(num_courses): if not dfs(c): return False return True
Time complexity: O(V + E)
Space complexity: O(V + E)