Compilation Order

Explanation & Solution

Description

You are given a list of source files and their dependencies represented as pairs [file, dependency], meaning that file depends on dependency and dependency must be compiled before file.

Return a valid compilation order such that every file is compiled after all of its dependencies. If there are multiple valid orderings, return any of them.

You may assume that the dependency graph has no cycles and that a valid compilation order always exists.

Input: dependencies = [["B","A"],["C","A"],["D","B"],["D","C"]]

Output:["A","B","C","D"]

Explanation: A has no dependencies so it is compiled first. B and C both depend on A. D depends on both B and C. A valid order is ["A", "B", "C", "D"] or ["A", "C", "B", "D"].

Constraints

1 <= dependencies.length <= 1000
dependencies[i].length == 2
Each element is a non-empty string
The dependency graph contains no cycles

Approach

Topological Sort pattern

1. Build the Dependency Graph

Create a directed graph where each edge goes from a dependency to the file that depends on it
For each pair [file, dep], add an edge dep → file
Track the in-degree of each node (number of dependencies it has)

2. Initialize the Queue

Find all files with in-degree 0 — these have no dependencies
Add them to the BFS queue as starting points

3. BFS Topological Sort

Dequeue a file, add it to the order result
For each file that depends on it, decrement that file's in-degree
When a file's in-degree reaches 0, all its dependencies are compiled — enqueue it

4. Return the Compilation Order

The order array now contains all files in a valid compilation sequence
Every file appears after all of its dependencies

Key Insight

This is a direct application of topological sort on a dependency graph
Dependencies naturally form a DAG (directed acyclic graph), and topological sort produces a linear ordering that respects all edges
Kahn's algorithm (BFS-based) processes nodes in layers: first those with no dependencies, then those whose dependencies are all satisfied

Time

O(V + E) where V = number of files and E = number of dependency pairs

Space

O(V + E) for the graph and auxiliary data structures

Solution Code

Alien Dictionary

Verifying an Alien Dictionary