Solution: Compilation Order

Explore how to solve the compilation order problem for classes using topological sort. Learn to build a graph from dependencies, identify sources, and traverse using BFS to produce a valid order while handling cycles. Understand the time and space complexity of this approach.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using topological sort

Statement

There are a total of $n$ classes labeled with the English alphabet ( $A$ , $B$ , $C$ , and so on). Some classes are dependent on other classes for compilation. For example, if class $B$ extends class $A$ , then $B$ has a dependency on $A$ . Therefore, $A$ must be compiled before $B$ .

Given an array of the dependency pairs, find the order in which the classes should be compiled.

Constraints:

Class name should be a character.
$0 \leq$ dependencies.length $\leq 676$
dependencies[i].length $= 2$

...