Smallest Study Order
MediumGraphs
Problem
A student must take n courses numbered 0 to n - 1. Each entry [a, b] of prereqs means course a must be taken before course b. Courses are taken one at a time.
Among all valid orders, return the lexicographically smallest one: at every step, take the lowest-numbered course whose prerequisites are all done. If no valid order exists, return an empty array.
Example 1
- Input:
- n = 4, prereqs = [[1, 0], [2, 0], [3, 1]]
- Output:
- [2, 3, 1, 0]
At the start 2 and 3 are available; take 2. Only 3 is available; taking it frees 1. Taking 1 frees 0.
Example 2
- Input:
- n = 3, prereqs = [[0, 1], [1, 2], [2, 0]]
- Output:
- []
The prerequisites form a cycle.
Example 3
- Input:
- n = 5, prereqs = []
- Output:
- [0, 1, 2, 3, 4]
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ prereqs.length ≤ 5·10^4
- 0 ≤ a, b < n
- Pairs may repeat.
Hint
Show the first hint
Kahn's algorithm produces a valid order by repeatedly taking a course with no remaining prerequisites. Which one should you take when several are ready?
Walkthrough
How to approach it
01Clarify before coding
- What does 'lexicographically smallest' mean here? Compare orders position by position; the first differing course decides.
- What if there is a cycle? Return an empty array.
- Can prerequisites repeat? Yes; count each copy in the in-degree and remove each copy when its source is taken.
02Brute force
Generate all permutations in lexicographic order and return the first that respects every prerequisite.
Cost: O(n!·m) in the worst case; even n = 12 is too slow.
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.