Unpack the core of topological sort, focusing on ordering dependencies and resolving compilation sequences efficiently.

Coding

Determines a valid linear ordering of nodes in a directed acyclic graph that has dependencies on each other, crucial in tasks like scheduling or dependency resolution.

Topological Sort

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# 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.  


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

Solution: Compilation Order

Statement▼

Solution: Compilation Order

Statement▼