All problems

Lexicographic Build Order

Medium · topological sort

A project has n modules, numbered 0 to n - 1. Some modules need others to be built first. These rules are given as a list needs of pairs [a, b], meaning module a must be built before module b.

A build order lists every module exactly once so that every rule is respected. Several orders may be valid. Return the one that comes first when orders are compared like words: look at the first position where two orders differ, and the order with the smaller module number there comes first.

If the rules contradict each other, so that no valid order exists, return an empty list. The same rule may be listed more than once, and a rule may even name a module as needing itself, which can never be satisfied.

Examples

Example 1

Input: n = 4, needs = [[3, 1], [2, 0]]

Output: [2, 0, 3, 1]

Modules 2 and 3 can start first and 2 is smaller, so build 2. That frees 0, which is now the smallest available, then 3, and finally 1.

Example 2

Input: n = 3, needs = [[0, 1], [1, 2]]

Output: [0, 1, 2]

The rules form a chain, so there is only one valid order.

Example 3

Input: n = 3, needs = [[0, 1], [1, 2], [2, 1]]

Output: []

Modules 1 and 2 each need the other built first, so none of the three can be completed.

Constraints