IRInterview Ready
← All patterns

Topological Sort

Order nodes of a DAG such that every directed edge u→v places u before v — via BFS (Kahn's algorithm, in-degree counting) or DFS (post-order reversal).

When to use it

  • Task scheduling with dependencies, course prerequisite ordering, build systems.

Signals in the problem statement

  • 'Prerequisite', 'must happen before', dependency graph input.

Common pitfalls

  • Not detecting a cycle (an invalid, unsatisfiable dependency graph) — Kahn's algorithm detects this naturally if not all nodes get processed.

Practice Problems

Course Schedule (Cycle Detection / Topo Sort)

Medium

Asked at: Google, Amazon, Meta

Given numCourses and prerequisite pairs [a, b] (must take b before a), determine if it's possible to finish all courses.

Time: O(V + E) · Space: O(V + E)