Solution: Compilation Order

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 a list of the dependency pairs, find the order in which the classes should be compiled.

Constraints:

• Class name should be an uppercase character.
• $0 \leq$ dependencies.length $\leq 676$
• dependencies[i].length $= 2$
• All dependency pairs should be unique.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to generate all possible compilation orders for the given classes and then select the ones that satisfy the dependencies.

However, this would be very expensive since there would be an exponential number of possible orders ( ${n!}$, where $n$ is the number of classes) and only a handful of valid ones. The time complexity for this approach is $O(n!)$. The space complexity is $O(1)$.

Optimized approach using topological sort

A more optimized solution to the above problem is topological ordering. Topological sort is used to find a linear ordering of elements that have dependencies on or priority over each other. For example, if $A$ is dependent on $B$ or if $B$ has priority over $A$, $B$ is listed before $A$ in topological order. Since we’re looking for the order of compilation of classes, this problem lends itself naturally to the topological sort pattern.

For this problem, we find the topological order of the given classes using the list of class dependencies. The vertices in the graph represent the classes, and the directed edge represents the dependency relationship.