beingsde
Sign In
Back to all DSA patterns
Graph / Topological Sort•Pattern: BFS / Topological Sort•Medium

Topological sort of a DAG (Kahn's algorithm)

Problem Intuition & Objective

Order nodes of a directed acyclic graph so all edges go from earlier to later.

Time ComplexityO(V+E)
Optimal
Space ComplexityO(V+E)
Memory Bounds
Optimal Algorithmic Approach

BFS (Kahn's): process in-degree 0 nodes iteratively.

Core Invariants & Edge Cases

  • Compute in-degrees; enqueue all zero-in-degree nodes
  • Process queue: decrement neighbors' in-degrees, enqueue those reaching 0
  • If result length < V, a cycle exists
Previous ProblemDijkstra's shortest path algorithmNext Problem Bellman-Ford — detect negative weight cycles

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.