Can Every Module Be Finished
MediumGraphs
Problem
A training programme has n modules numbered 0 to n - 1. Each entry [a, b] of prereqs means module a must be completed before module b.
Return true if there is some way to complete every module, and false if circular requirements make that impossible.
Example 1
- Input:
- n = 3, prereqs = [[0, 1], [1, 2]]
- Output:
- true
Take 0, then 1, then 2.
Example 2
- Input:
- n = 3, prereqs = [[0, 1], [1, 2], [2, 0]]
- Output:
- false
0 needs 2, 2 needs 1 and 1 needs 0: a circle.
Example 3
- Input:
- n = 4, prereqs = [[0, 1], [2, 3], [3, 2]]
- Output:
- false
0 and 1 are fine, but 2 and 3 wait on each other.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ prereqs.length ≤ 5·10^4
- 0 ≤ a, b < n
- Pairs may repeat; [a, a] means a module requires itself.
Hint
Show the first hint
Model modules as nodes and prerequisites as arrows. What shape must the graph have for a valid order to exist?
Walkthrough
How to approach it
01Clarify before coding
- Which direction does [a, b] point? From a to b: a is the prerequisite of b.
- Do I need the order itself? No, only whether one exists.
- Can the graph be disconnected? Yes; every part must be cycle-free.
02Brute force
Try every permutation of modules and check whether one respects all prerequisites.
Cost: O(n!·m): hopeless beyond n ≈ 10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.