Course Schedule
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: trueExplanation: First take course 1 (no prerequisites) and then take course 0.
Example 2:
Input: numCourses = 2, prerequisites = [[0,1],[1,0]]
Output: falseExplanation: 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 <= 10000 <= prerequisites.length <= 1000prerequisites[i].length == 20 <= a[i], b[i] < numCourses- All
prerequisitepairs are unique.
Recommended Time & 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.