680. Course Plan Feasible
A student must complete n courses numbered 0 to n-1. Each entry prerequisites[i] = [a, b] says that course b has to be finished before course a can be started. The student takes one course at a time and may order the courses however they like, subject to those rules.
Return true if there is an order in which all n courses can be finished, otherwise false. Pairs may repeat, and a pair such as [3, 3] (a course that requires itself) makes the plan impossible. Courses that appear in no pair can be taken at any time. Use an iterative method; the expected cost is O(n + m) time and O(n + m) space for m pairs.
Example 1
- Input:
- n = 5, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3]]
- Output:
- true
- Explanation:
Take 0, then 1 and 2, then 3, then 4; every prerequisite is met, so the answer is true.
Example 2
- Input:
- n = 4, prerequisites = [[1,0],[2,1],[3,2],[1,3]]
- Output:
- false
- Explanation:
Courses 1, 2 and 3 each wait on another one of them in a loop (1 needs 3, 3 needs 2, 2 needs 1), so none of them can ever start.
Example 3
- Input:
- n = 3, prerequisites = []
- Output:
- true
- Explanation:
With no prerequisites the courses can be taken in any order.
Constraints
1 ≤ n ≤ 100000
0 ≤ prerequisites.length ≤ 200000
0 ≤ a, b < n; pairs may repeat
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)