Why it works
- A pair [a, b] is an arrow b → a, so the in-degree of a course is the number of courses that must come before it.
- A course is added to the order only after every course with an arrow into it, so the order keeps every pair.
- If there is a loop, the courses on it never reach in-degree 0: the order comes out shorter than n, and the answer is an empty list.
Complexity
Time O(n + p) for n courses and p pairs: each pair is read once, each course enters the queue at most once and each arrow is followed once. Memory O(n + p) for the arrows, the in-degrees, the queue and the order.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗