Solution: Compilation Order

Let's solve the Compilation Order problem using the Topological Sort pattern.

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 a list 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$
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.

From the example above, we get the order $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$ . Two other possible orderings of the classes above can be $A \rightarrow C \rightarrow B \rightarrow D \rightarrow E$ or $A \rightarrow C \rightarrow D \rightarrow B \rightarrow E$ . This order of graph vertices is known as a topological sorted order.

We can say that a topological ordering starts with one of the sources and ends at one of the sinks:

Source: Any vertex with no incoming edge and only outgoing edges is called a source.
Sink: Any vertex that has only incoming edges and no outgoing edge is called a sink.

The illustration below gives a rundown of the solution:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

To find the topological sort of a graph, we use a breadth-first search (BFS) approach for traversing the vertices.

We store the graph in adjacency lists in which each parent vertex has a list containing all of its children. For example, in the above slide deck, the adjacency list for vertex $A$ would be $[C, B]$ . To find the sources, we maintain a hash map to count the in-degrees, which is the count of incoming edges of a vertex. Any vertex with a $0$ in-degree is a source. We store the topological order in a list called sorted order.

Here is how we implement this solution:

We initialize the graph with an empty adjacency list for each vertex. The vertices will have an in-degree of $0$ . If the length of the graph is $0$ , that is, there are no vertices, we’ll return an empty list.

import java.util.*;
class CompilationOrder {
    
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        // a. Initialize the graph and inDegree
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        System.out.println("\tInitializing the graph and inDegree");
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        System.out.println("\t\tGraph: " + graph);
        System.out.println("\t\tinDegree: " + inDegree + "\n");
        if(graph.size() <= 0){
            System.out.println("\tThere are no vertices");
            System.out.println("\t\tReturning the sorted order: " + sortedOrder);
        }
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Initializing the graph

import java.util.*;
class CompilationOrder {
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        // a. Initialize the graph and inDegree
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        System.out.println("\tInitializing the graph and inDegree");
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        System.out.println("\t\tGraph: " + graph);
        System.out.println("\t\tinDegree: " + inDegree + "\n");
        if(graph.size() <= 0){
            System.out.println("\tThere are no vertices");
            System.out.println("\t\tReturning the sorted order: " + sortedOrder);
            return sortedOrder;
        }
        System.out.println("\tBuilding the graph and populating inDegree");
        // b. Build the graph
        int k = 0;
        for (int dependency = 0; dependency < dependencies.size(); dependency++){
            System.out.println("\t\tLoop index: " + k);
            k += 1;
            char parent = dependencies.get(dependency).get(1);
            char child = dependencies.get(dependency).get(0);
            graph.get(parent).add(child); // put the child into it's parent's list
            inDegree.put(child, inDegree.get(child) + 1); // increment child's inDegree
            System.out.println("\t\t\tDependency pair: " + dependencies.get(dependency) + " ⟶ parent: " + parent + ", child: " + child);
            System.out.println("\t\t\tAppending the child to the parent's list in the graph:");
            System.out.println("\t\t\t\tGraph: " + graph);
            System.out.println("\t\t\tIncrementing indegree of the child ⟶ " + inDegree);
        }
        System.out.println();
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Building the graph

import java.util.*;
class CompilationOrder {
    
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        // a. Initialize the graph and inDegree
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        System.out.println("\tInitializing the graph and inDegree");
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        System.out.println("\t\tGraph: " + graph);
        System.out.println("\t\tinDegree: " + inDegree + "\n");
        if(graph.size() <= 0){
            System.out.println("\tThere are no vertices");
            System.out.println("\t\tReturning the sorted order: " + sortedOrder);
            return sortedOrder;
        }
        System.out.println("\tBuilding the graph and populating inDegree");
        // b. Build the graph
        int k = 0;
        for (int dependency = 0; dependency < dependencies.size(); dependency++){
            System.out.println("\t\tLoop index: " + k);
            k += 1;
            char parent = dependencies.get(dependency).get(1);
            char child = dependencies.get(dependency).get(0);
            graph.get(parent).add(child); // put the child into it's parent's list
            inDegree.put(child, inDegree.get(child) + 1); // increment child's inDegree
            System.out.println("\t\t\tDependency pair: " + dependencies.get(dependency) + " ⟶ parent: " + parent + ", child: " + child);
            System.out.println("\t\t\tAppending the child to the parent's list in the graph:");
            System.out.println("\t\t\t\tGraph: " + graph);
            System.out.println("\t\t\tIncrementing indegree of the child ⟶ " + inDegree);
        }
        System.out.println();
        // c. Find all sources i.e., all n with 0 in-degrees
        System.out.println("\n\tFinding all sources");
        Queue<Character> sources = new LinkedList<>();
        int l = 0;
        for(char key : inDegree.keySet()){
            System.out.println("\t\tLoop index: " + l );
            l += 1;
            if(inDegree.get(key) == 0){
                sources.add(key);
                System.out.println("\t\t\tIn-degree of " + key + " is 0, hence it's a source");
                System.out.println("\t\t\tSources: " + sources);
            }
            else
                System.out.println("\t\t\tIn-degree of " + key + " is " + inDegree.get(key) + " hence it's not a source");
        }
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Identify the sources

import java.util.*;
class CompilationOrder {
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        // a. Initialize the graph and inDegree
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        System.out.println("\tInitializing the graph and inDegree");
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        System.out.println("\t\tGraph: " + graph);
        System.out.println("\t\tinDegree: " + inDegree + "\n");
        if(graph.size() <= 0){
            System.out.println("\tThere are no vertices");
            System.out.println("\t\tReturning the sorted order: " + sortedOrder);
            return sortedOrder;
        }
        System.out.println("\tBuilding the graph and populating inDegree");
        // b. Build the graph
        int k = 0;
        for (int dependency = 0; dependency < dependencies.size(); dependency++){
            System.out.println("\t\tLoop index: " + k);
            k += 1;
            char parent = dependencies.get(dependency).get(1);
            char child = dependencies.get(dependency).get(0);
            graph.get(parent).add(child); // put the child into it's parent's list
            inDegree.put(child, inDegree.get(child) + 1); // increment child's inDegree
            System.out.println("\t\t\tDependency pair: " + dependencies.get(dependency) + " ⟶ parent: " + parent + ", child: " + child);
            System.out.println("\t\t\tAppending the child to the parent's list in the graph:");
            System.out.println("\t\t\t\tGraph: " + graph);
            System.out.println("\t\t\tIncrementing indegree of the child ⟶ " + inDegree);
        }
        System.out.println();
        // c. Find all sources i.e., all n with 0 in-degrees
        System.out.println("\n\tFinding all sources");
        Queue<Character> sources = new LinkedList<>();
        int l = 0;
        for(char key : inDegree.keySet()){
            System.out.println("\t\tLoop index: " + l );
            l += 1;
            if(inDegree.get(key) == 0){
                sources.add(key);
                System.out.println("\t\t\tIn-degree of " + key + " is 0, hence it's a source");
                System.out.println("\t\t\tSources: " + sources);
            }
            else
                System.out.println("\t\t\tIn-degree of " + key + " is " + inDegree.get(key) + " hence it's not a source");
        }
        System.out.println();
        // d. For each source, add it to the sorted_order and subtract one from all of its children's in-degrees
        // if a child's in-degree becomes zero, add it to the sources queue
        System.out.println("\n\tRemoving the sources from the graph");
        int m = 0;
        while(!sources.isEmpty()){
            System.out.println("\t\tLoop index: " + m);
            m += 1;
            System.out.println("\t\tGetting the source by popping from the queue");
            System.out.print("\t\t\tSources: " + sources + " ⟶ " );
            char vertex = sources.poll();
            System.out.println(sources);
            System.out.println("\t\t\tVertex: " + vertex);
            System.out.print("\t\t\tAppending to the sorted order list: " + sortedOrder + " ⟶ ");
            sortedOrder.add(vertex);
            System.out.println(sortedOrder);
            System.out.println("\t\t\tUpdating the in-degrees of the children");
            System.out.println("\t\t\t\tSource: " + vertex + ", children: " + graph.get(vertex));
            int n = 0;
            for(int child = 0; child < graph.get(vertex).size(); child++){
                System.out.println("\t\t\t\tInner loop index: " + n);
                n += 1;
                System.out.println("\t\t\t\t\tChild: " + graph.get(vertex).get(child));
                System.out.println("\t\t\t\t\tDecrementing in-degree of " + graph.get(vertex).get(child) + ": " + inDegree.get(graph.get(vertex).get(child))+ " ⟶ "+ (inDegree.get(graph.get(vertex).get(child)) - 1));
                inDegree.put(graph.get(vertex).get(child), inDegree.get(graph.get(vertex).get(child)) -1);
                if(inDegree.get(graph.get(vertex).get(child)) == 0){
                    System.out.println("\t\t\t\t\tSince in-degree of " + graph.get(vertex).get(child) + " = 0, it's now a source.");
                    System.out.print("\t\t\t\t\tAdding it to the sources queue: " + sources + " ⟶ ");
                    sources.add(graph.get(vertex).get(child));
                    System.out.println(sources);
                }
            }
        }
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Updating the in-degrees and removing the sources from the graph

import java.util.*;
class CompilationOrder {
    
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        // a. Initialize the graph and inDegree
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        System.out.println("\tInitializing the graph and inDegree");
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        System.out.println("\t\tGraph: " + graph);
        System.out.println("\t\tinDegree: " + inDegree + "\n");
        if(graph.size() <= 0){
            System.out.println("\tThere are no vertices");
            System.out.println("\t\tReturning the sorted order: " + sortedOrder);
            return sortedOrder;
        }
        System.out.println("\tBuilding the graph and populating inDegree");
        // b. Build the graph
        int k = 0;
        for (int dependency = 0; dependency < dependencies.size(); dependency++){
            System.out.println("\t\tLoop index: " + k);
            k += 1;
            char parent = dependencies.get(dependency).get(1);
            char child = dependencies.get(dependency).get(0);
            graph.get(parent).add(child); // put the child into it's parent's list
            inDegree.put(child, inDegree.get(child) + 1); // increment child's inDegree
            System.out.println("\t\t\tDependency pair: " + dependencies.get(dependency) + " ⟶ parent: " + parent + ", child: " + child);
            System.out.println("\t\t\tAppending the child to the parent's list in the graph:");
            System.out.println("\t\t\t\tGraph: " + graph);
            System.out.println("\t\t\tIncrementing indegree of the child ⟶ " + inDegree);
        }
        System.out.println();
        // c. Find all sources i.e., all n with 0 in-degrees
        System.out.println("\n\tFinding all sources");
        Queue<Character> sources = new LinkedList<>();
        int l = 0;
        for(char key : inDegree.keySet()){
            System.out.println("\t\tLoop index: " + l );
            l += 1;
            if(inDegree.get(key) == 0){
                sources.add(key);
                System.out.println("\t\t\tIn-degree of " + key + " is 0, hence it's a source");
                System.out.println("\t\t\tSources: " + sources);
            }
            else
                System.out.println("\t\t\tIn-degree of " + key + " is " + inDegree.get(key) + " hence it's not a source");
        }
        System.out.println();
        // d. For each source, add it to the sorted_order and subtract one from all of its children's in-degrees
        // if a child's in-degree becomes zero, add it to the sources queue
        System.out.println("\n\tRemoving the sources from the graph");
        int m = 0;
        while(!sources.isEmpty()){
            System.out.println("\t\tLoop index: " + m);
            m += 1;
            System.out.println("\t\tGetting the source by popping from the queue");
            System.out.print("\t\t\tSources: " + sources + " ⟶ " );
            char vertex = sources.poll();
            System.out.println(sources);
            System.out.println("\t\t\tVertex: " + vertex);
            System.out.print("\t\t\tAppending to the sorted order list: " + sortedOrder + " ⟶ ");
            sortedOrder.add(vertex);
            System.out.println(sortedOrder);
            System.out.println("\t\t\tUpdating the in-degrees of the children");
            System.out.println("\t\t\t\tSource: " + vertex + ", children: " + graph.get(vertex));
            int n = 0;
            for(int child = 0; child < graph.get(vertex).size(); child++){
                System.out.println("\t\t\t\tInner loop index: " + n);
                n += 1;
                System.out.println("\t\t\t\t\tChild: " + graph.get(vertex).get(child));
                System.out.println("\t\t\t\t\tDecrementing in-degree of " + graph.get(vertex).get(child) + ": " + inDegree.get(graph.get(vertex).get(child))+ " ⟶ "+ (inDegree.get(graph.get(vertex).get(child)) - 1));
                inDegree.put(graph.get(vertex).get(child), inDegree.get(graph.get(vertex).get(child)) -1);
                if(inDegree.get(graph.get(vertex).get(child)) == 0){
                    System.out.println("\t\t\t\t\tSince in-degree of " + graph.get(vertex).get(child) + " = 0, it's now a source.");
                    System.out.print("\t\t\t\t\tAdding it to the sources queue: " + sources + " ⟶ ");
                    sources.add(graph.get(vertex).get(child));
                    System.out.println(sources);
                }
            }
        }
        // topological sort is not possible as the graph has a cycle
        if(sortedOrder.size() != graph.size()){
            System.out.println("\n\tLength of the sorted order list = " + sortedOrder.size());
            System.out.println("\tLength of the graph = " + graph.size());
            System.out.println("\t\tSince the lengths are not equal, there's a cycle in the graph.");
            return new ArrayList<>();
        }
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Compilation Order

import java.util.*;
class CompilationOrder {
    public static String repeat(String str, int pValue){
        String out = "";
        for(int i = 0; i < pValue; i++)
        {
            out += str;
        }
        return out;
    }
    public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies){
        List<Character> sortedOrder = new ArrayList<>();
        
        HashMap<Character, List<Character>> graph = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>(); 
        for( int x = 0; x < dependencies.size(); x++){
            char parent = dependencies.get(x).get(0);
            char child = dependencies.get(x).get(1);
            graph.put(parent, new ArrayList<>());
            graph.put(child, new ArrayList<>());
            inDegree.put(parent, 0);
            inDegree.put(child, 0);
        }
        if(graph.size() <= 0){
            return sortedOrder;
        }
        for (int dependency = 0; dependency < dependencies.size(); dependency++){
            char parent = dependencies.get(dependency).get(1);
            char child = dependencies.get(dependency).get(0);
            graph.get(parent).add(child); 
            inDegree.put(child, inDegree.get(child) + 1);
        }
        Queue<Character> sources = new LinkedList<>();
        for(char key : inDegree.keySet()){
            if(inDegree.get(key) == 0){
                sources.add(key);
            }
        }
        while(!sources.isEmpty()){
            char vertex = sources.poll();
            
            sortedOrder.add(vertex);
            for(int child = 0; child < graph.get(vertex).size(); child++){
                inDegree.put(graph.get(vertex).get(child), inDegree.get(graph.get(vertex).get(child)) -1);
                if(inDegree.get(graph.get(vertex).get(child)) == 0){
                    sources.add(graph.get(vertex).get(child));
                }
            }
        }
        if(sortedOrder.size() != graph.size()){
            return new ArrayList<>();
        }
        return sortedOrder;
    }
    public static void main( String args[] ) {
        ArrayList<ArrayList<ArrayList<Character>>> dependencies = new ArrayList<ArrayList<ArrayList<Character>>>() {
        {
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('D', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('E', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'D')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'E')));
                    add(new ArrayList<Character>(Arrays.asList('F', 'C')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('A', 'B')));
                    add(new ArrayList<Character>(Arrays.asList('B', 'A')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('B', 'C')));
                    add(new ArrayList<Character>(Arrays.asList('C', 'A')));
                    add(new ArrayList<Character>(Arrays.asList('A', 'F')));
                }
            });
            add(new ArrayList<ArrayList<Character>>() {
                {
                    add(new ArrayList<Character>(Arrays.asList('C', 'C')));
                }
            });
        }
        };
        for(int i = 0; i < dependencies.size(); i++){
            System.out.println(i + 1 + ".\tdependencies: " + dependencies.get(i));
            System.out.println("\tCompilation Order: " + findCompilationOrder(dependencies.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}

Compilation Order

Solution summary

To recap, the solution to this problem can be divided into the following parts:

Build a graph from the dependencies list and keep track of the in-degrees of vertices in a hash map.
Populate the sources deque with vertices with in-degrees $= 0$ .
Add the sources to the sorted list.
Remove the sources from the graph and update the in-degrees of their children. If the in-degree of a child becomes $0$ , it becomes a source in the next iteration.
Repeat until all vertices are visited.

Time complexity

The time complexity of the above algorithm is $O(V+E)$ , where $V$ is the total number of vertices and $E$ is the total number of edges in the graph.

Space complexity

The space complexity is $O(V + E)$ because we are creating a deque data structure that will have $O(V)$ elements in the worst case. We are also maintaining a hash table with the in-degree of the vertices, which also has a size of $O(V)$ . Additionally, the solution creates a graph with $O(E)$ edges, where $E$ is the total number of dependencies, contributing to the overall space complexity.

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

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion