Solution: Compilation Order

Statement

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

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≤0 \leq dependencies.length ≤676\leq 676
  • dependencies[i].length =2= 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!{n!}, where nn is the number of classes) and only a handful of valid ones. The time complexity for this approach is O(n!)O(n!). The space complexity is O(1)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 AA is dependent on BB or if BB has priority over AA, BB is listed before AA 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.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.