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 …

compilation-order.js

export function findCompilationOrder(dependencies) {
  const adjList = {};
  // store indegree of each vertex (indegree = how many edges are inbound)
  const indegrees = {};

  // initialize our adj list and indegrees map
  for (let i = 0; i < dependencies.length; ++i) {
    const [to, from] = dependencies[i];
    adjList[from] = [];
    adjList[to] = [];
    indegrees[from] = 0;
    indegrees[to] = 0;
  }

  // build our adj list, and increment indegree of each vertex
  for (let i = 0; i < dependencies.length; ++i) {
    const [to, from] = dependencies[i];
    adjList[from].push(to);
    indegrees[to] = (indegrees[to] ?? 0) + 1;
  }

  // final sorted result
  const result = [];
  // store vertices to process
  const queue = [];

  // find initial sources (vertex with indegree = 0)
  // add them to the queue
  Object.keys(indegrees).forEach((vertex) => {
    if (indegrees[vertex] === 0) {
      queue.push(vertex);
    }
  });

  while (queue.length > 0) {
    // add vertex from queue to result
    const vertex = queue.shift();
    result.push(vertex);
    // iterate vertex children
    const children = adjList[vertex];
    for (let i = 0; i < children.length; i++) {
      // for each children, decrement their indegree,
      // because their parent dependency is processed
      const childVertex = children[i];
      indegrees[childVertex] -= 1;
      // if the new indegree is 0, add it to queue
      if (indegrees[childVertex] === 0) {
        queue.push(childVertex);
      }
    }
  }

  // handle cycles in the graph by comparing the result length
  // the result length should always be equal to V
  if (result.length !== Object.keys(adjList).length) {
    return [];
  }

  return result;
}

// tc: O(V + E)
// sc: O(V)