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

Course schedule — detect cycle in directed graph

Problem Intuition & Objective

Determine if you can finish all courses given prerequisites (i.e., no cycle exists).

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

Kahn's BFS: track in-degrees, process zero-in-degree nodes, check count at end.

Core Invariants & Edge Cases

  • Model as directed graph; a cycle means impossible
  • Kahn's algorithm (BFS + in-degree) or DFS with 3-color marking
  • If topological sort includes all nodes, no cycle exists
Previous ProblemNumber of islands (connected components in grid)Next Problem Clone a graph

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.