Course Schedule

Medium#207

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. Find out whether all the courses can be taken. Our example: 6 courses and the pairs [1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4], [5, 3]. The answer is false: courses 1, 2 and 3 each wait for another one of them.

207 Course ScheduleWalkthrough · 1×

Example: 6 courses; an arrow b → a for each pair [a, b]. The number above a course is its in-degree: how many courses it still waits for.

001221314152queuefront on the left—taken—
waits for other coursesin the queuecurrent coursewhere the arrow leads; at the end, the looptaken

Each pair [a, b] puts b before a: [1, 0], [2, 1], [3, 2], [1, 3], [4, 0], [5, 4], [5, 3] give the arrows 0 → 1, 1 → 2, 2 → 3, 3 → 1, 0 → 4, 4 → 5, 3 → 5. Count the arrows into each course

01/19
restart · back · play · step
Speed
1function canFinish(n, prerequisites):
2 graph, indegree = an arrow b → a for each [a, b]
3 queue = courses with indegree 0
4 taken = 0
5 while queue is not empty:
6 course = queue.popFront()
7 taken += 1
8 for next in graph[course]:
9 decrease indegree[next] by 1
10 if indegree[next] is 0:
11 queue.pushBack(next)
12 return taken == n
state
n
6
indegree
[0, 2, 1, 1, 1, 2]
queue
–
taken
–
course
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A course enters the queue only when every course before it is taken, so the courses come out of the queue in an order that keeps every pair.
  2. On a loop each course waits for the one before it on the loop. None of them ever reaches in-degree 0, so none is taken, and neither is any course after the loop.
  3. So all n courses are taken exactly when there is no loop: counting the taken courses answers the question.

Complexity

Time O(n + p) for n courses and p pairs: each course enters the queue at most once and each arrow is followed at most once. Memory O(n + p) for the arrows, the in-degrees and the queue.

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.