There are numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] means that you must take course bi before course ai.
For example, the pair [0, 1] means that to take course 0 you have to take course 1 first.
Return an order in which you can take all the courses, as a slice of course numbers. A course is ready when all of its prerequisites are taken. Whenever several courses are ready, take the one with the smallest number next: this rule makes the order unique. If it is impossible to take all the courses, return an empty slice.
Example 1:
Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Explanation: Draw each pair [a, b] as an arrow b → a, from the course to take first:
0 → 1 → 3
0 → 2 → 3
At the start only course 0 is ready. Once it is taken, courses 1 and 2 are both ready: 1 is smaller,
so it comes first, then 2. Course 3 is ready last, when both 1 and 2 are taken.
The order 0, 2, 1, 3 also takes every course after its prerequisites, but it takes 2 while the
smaller course 1 is ready, so it is not the answer.
Example 2:
Input: numCourses = 5, prerequisites = [[1, 4], [0, 4], [2, 3]] Output: [3, 2, 4, 0, 1] Explanation: Courses 3 and 4 need nothing. 3 is smaller, so it comes first, and taking it makes course 2 ready. Now 2 and 4 are ready, and 2 is smaller. Taking 4 makes courses 0 and 1 ready, and they come last, the smaller one first.
Example 3:
Input: numCourses = 3, prerequisites = [[1, 0], [2, 1], [1, 2]] Output: [] Explanation: Course 1 needs course 2 first, and course 2 needs course 1 first: they wait for each other (a cycle), so neither of them can ever be taken. Course 0 can be taken, but not all the courses, so the answer is empty.
Constraints:
1 <= numCourses <= 1050 <= prerequisites.length <= 105prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi- All the pairs
prerequisites[i]are distinct.
Note:
Your algorithm should run in O((V + E) log V) time, where V is numCourses and E is the number of pairs, and use O(V + E) extra space.
The tutorial uses Kahn's algorithm, as in Course Schedule, with one change: the courses that are ready wait in a min-heap instead of a queue, so the next course taken is always the smallest ready one. Each course enters and leaves the heap once, in O(log V) each. If fewer than numCourses courses get taken, the rest wait on a cycle, or on a course that does, and no order exists. Looking through all the courses for the smallest ready one before each pick would cost O(V2) instead.
Free plan: 30 tutor messages. PRO is unlimited.
