Graphs Topological sort
456. Course Schedule II
There are numCourses courses, numbered from 0 to numCourses - 1. Each pair [a, b] in prerequisites
means you must finish course b before you start course a.
Return an order in which you can take every course: each course appears exactly once, after all of its prerequisites. If no such order exists, return an empty array.
Often several orders work, and any of them is correct. The result shows a valid order when the order you
return is one. An empty array shows as []. Any other answer shows what is wrong with it, such as
course 3 comes before course 1, which it needs.
Example 1
Input: numCourses = 5
prerequisites = [[3, 0], [3, 1], [4, 3], [2, 4]]
[0,1,3,4,2]Explanation: Courses 0 and 1 need nothing. Course 3 needs both of them, course 4 needs 3, and course 2 needs 4.
[1,0,3,4,2] is also correct.
Example 2
Input: numCourses = 4
prerequisites = [[1, 0], [2, 1], [1, 2], [3, 0]]
[]Explanation: Course 1 needs 2, and course 2 needs 1. Neither can go first, so no order works, even though courses 0 and 3 are fine.
Example 3
Input: numCourses = 3, prerequisites = []
[0,1,2]Explanation: Nothing has to come first, so any of the six orders of the three courses is correct.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ numCourses ≤ 1050 ≤ prerequisites.length ≤ 105prerequisites[i].length == 20 ≤ ai, bi < numCourses
Clarifying questions
What you would ask an interviewer before writing any code.