The Runtime Theory
mediumLeetCode#topological-sort#cycle-detection

Course Schedule

Determine whether every course can be completed given prerequisite dependencies.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innumCourses=2, prerequisites=[[1,0]]

outtrue

innumCourses=2, prerequisites=[[1,0],[0,1]]

outfalse

innumCourses=3, prerequisites=[]

outtrue

Determine whether every course can be completed given prerequisite dependencies.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain time and space costs in terms of input size and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs.

Reasoning prompt

Use indegrees with Kahn’s algorithm or DFS states. A back-edge into the active path proves a cycle.

Use the linked judge for the canonical challenge. The examples above are compact TRT checks; create additional tests around the boundary most likely to break your invariant.

More practice in this topic

hard · graphsAlien Dictionarymedium · graphsCheapest Flights Within K Stopsmedium · graphsClone Graph

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save