Problem Brief

Compilation Order with Topological Sort

FULLTIMEONSITE INTERVIEW

You are given a list of module names and a list of dependency pairs. Each dependency [a, b] means module a depends on module b, so b must be compiled before a.

Return one valid compilation order that includes every module exactly once. If multiple modules are currently available to compile, choose the lexicographically smallest available module first so the result is deterministic.

If the dependency graph contains a cycle, return a single-element array ["IMPOSSIBLE"].

Function Description

Complete the function compilationOrder in the editor below.

compilationOrder has the following parameters:

String[] modules: all module names
String[][] dependencies: dependency pairs [module, prerequisite]

Returns

String[]: a valid compilation order, or ["IMPOSSIBLE"] if the dependencies contain a cycle.

1Example 1

Input

modules = ["A", "B", "C", "D"], dependencies = [["A", "B"], ["A", "C"], ["D", "A"]]

Output

["B", "C", "A", "D"]

Explanation

Both B and C are initially available, so lexicographical order chooses B before C.

2Example 2

Input

modules = ["A", "B"], dependencies = [["A", "B"], ["B", "A"]]

Output

["IMPOSSIBLE"]

Explanation

The two modules depend on each other, so no valid compilation order exists.

Constraints

Limits and guarantees your solution can rely on.

1 <= modules.length <= 2 * 10^5
0 <= dependencies.length <= 2 * 10^5
All module names are distinct.