Course Schedule II

Medium#210

There are n courses, numbered from 0 to n − 1, and a list of pairs [a, b]: course b has to be taken before course a. Return an order in which all the courses can be taken; any such order will do. If there is none, return an empty list. Our example: 6 courses and the pairs [0, 3], [0, 5], [1, 0], [2, 5], [4, 1], [4, 2]. One answer is [3, 5, 0, 2, 1, 4].

210 Course Schedule IIWalkthrough · 1×

Example: 6 courses and 6 pairs. The arrows are drawn as the pairs are read, b → a for [a, b]; the number above a course is how many courses it still waits for.

001020304050queuefront on the left—order—
waits for other coursesin the queuecurrent course; b of the pairwhere the arrow leadsin the order

No arrows yet: an empty list of next courses for each course

01/53
restart · back · play · step
Speed
1function findOrder(n, prerequisites):
2 graph = an empty list for each course
3 indegree = 0 for each course
4 for each [a, b] in prerequisites:
5 graph[b].pushBack(a)
6 increase indegree[a] by 1
7 queue = courses with indegree 0
8 order = []
9 while queue is not empty:
10 course = queue.popFront()
11 order.pushBack(course)
12 for next in graph[course]:
13 decrease indegree[next] by 1
14 if indegree[next] is 0:
15 queue.pushBack(next)
16 if length(order) < n:
17 return []
18 return order
state
a
–
b
–
indegree
–
queue
–
order
–
course
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. 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.
  2. A course is added to the order only after every course with an arrow into it, so the order keeps every pair.
  3. 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 ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.