Lesson overview · Free interview practice

Topological Sort

Order tasks based on dependencies using topological sort.

Topics in the full lesson
  • Concept and Use Cases
  • When to Use
  • Time and Space Complexity
  • Approaches to Topological Sort
  • Topological Sort using Kahn’s Algorithm (BFS)
  • Topological Sort using Depth-First Search (DFS)
  • Task Scheduling with Dependencies

Try the free interview questions

Work through a question before revealing its explanation. These questions and answers are free; Premium adds the full lesson walkthrough, examples and implementation detail.

CodingMedium

Course Schedule II

Question

There are numCourses courses labeled 0..numCourses-1 with a list of prerequisites ([a, b] meaning b must come before a). Return any valid ordering in which to take the courses, or an empty array if it's impossible (cycle exists). Solve with topological sort.

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Question

A tree is an undirected graph where any two vertices are connected by exactly one path. For a tree with n nodes labeled 0..n-1 and n-1 edges, you can pick any node as the root. The result is a rooted tree with some height. Return all root labels that minimize the resulting tree height (Minimum Height Trees, MHTs).

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Question

There is a new alien language whose alphabet you don't know. You are given a list of words sorted lexicographically by the rules of this alien language. Derive the order of letters in the alien language. If multiple valid orders exist, return any. If no valid order exists (the input is inconsistent), return "".

Take a moment to think about this before revealing the answer

Explain your reasoning or try an implementation before comparing answers.

Explore the full Topological Sort material

Premium includes the complete lessons and implementation references. Free practice questions remain available without a subscription.

All course tracks & premium content
From basics to advanced masterclasses
Built for JS/TS developers like you
Real-world tips & common pitfalls
Upgrade to Premium

Continue in this section