An online school has courses numbered 0 to courses - 1. Each pair [a, b] in prereqs means course b must be finished before course a. Write a function that returns whether a student could finish every course in some order.
An arrow means "unlocks". On the right, each course waits for another in the loop, so none can start.
The first is possible in the order 0, 1, 2. In the second, each course waits for the other. In the third, 0 → 1 → 2 → 0 is a loop, so none of those three can start.
Write can_finish_all(courses, prereqs) in Python or canFinishAll(courses, prereqs) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Model it as a directed graph
Draw an edge b → a for each pair: "b unlocks a". Everything can be finished exactly when this graph has no cycle.
Step 2
Start with what's available
A course with no unfinished prerequisites can be taken right away. Count each course's prerequisites (its in-degree). Put every course with a count of 0 in a queue.
Step 3
Taking a course unlocks others
Take a course from the queue and count it as finished. For each course it unlocks, lower that course's count by one; when a count hits 0, that course is now available, so add it to the queue.
Step by step1 / 3
Numbers are prerequisites still needed. Course 0 needs none: take it.
Step 4
Read the answer
If you finished all the courses, there was no cycle. If some were never available, they're stuck in (or behind) a cycle. This is Kahn's algorithm, and the finishing order it produces is a valid course plan.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Build an adjacency list unlocks[b] and an in-degree count for each course. Queue all courses with in-degree 0. Repeatedly take one, count it, and decrease the in-degree of each course it unlocks, queueing those that reach 0. Return whether the number taken equals courses.
python
1from collections import deque
2
3
4def can_finish_all(courses, prereqs):
5 unlocks = [[] for _ in range(courses)]
6 waiting_on = [0] * courses # how many prerequisites each course still needs
↑prerequisites still needed
7 for course, needs in prereqs:
8 unlocks[needs].append(course)
9 waiting_on[course] += 1
10 ready = deque(c for c in range(courses) if waiting_on[c] == 0)