Loading page…
Practice problem · easy
You work on an online shop that sells video courses. A course can have prerequisites: you must finish another course first. The shop has n courses, numbered 0 to n - 1.
Before a new bundle goes on sale, the shop checks that a learner could really finish every course in it. If the prerequisites form a loop, such as course 1 needing course 2 and course 2 needing course 1, nobody could finish those courses.
Write can_finish(n, prereqs).
n is the number of courses.prereqs[i] = [course, required] means you must finish required before you can start course.True when the courses can be finished in some order, one at a time. Return False otherwise.Input: n = 4, prereqs = [[1, 0], [2, 1], [3, 2]]
Output: trueA chain: 1 needs 0, 2 needs 1, and 3 needs 2. Count the prerequisites each course still has, and keep the courses with none in a queue.
| Round | Queue | Take | Taken so far |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 2 | 1 | 1 | 2 |
| 3 | 2 | 2 | 3 |
| 4 | 3 | 3 | 4 |
All 4 courses were taken, so the answer is true.
Input: n = 2, prereqs = [[1, 0], [0, 1]]
Output: falseCourse 1 needs 0, and course 0 needs 1. Neither can start, so the queue is empty from the beginning and 0 courses are taken.
Input: n = 3, prereqs = []
Output: trueThere are no prerequisites, so every course can be taken.
1 ≤ n ≤ 100,0000 ≤ len(prereqs) ≤ 200,000, and every row is [course, required] with 0 ≤ course, required < n and course ≠ requiredThere can be 100,000 courses and 200,000 prerequisites. Going over every prerequisite again for each course would be n × m: 20 billion steps. The answer must touch each course and each prerequisite only a few times, which is n + m: 300,000 steps. Counting prerequisites does that.
can_finish · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.