Vibe Engines Learn
CODING CHALLENGE · N°43

Course Schedule (Cycle Detection)

Medium GraphsTopological SortBFS

Can you finish every course given its prerequisites? It’s the classic "is this dependency graph acyclic?" question — the same check a build system or package manager runs before scheduling work. Detect a cycle with a topological sort. Solve it in Python or TypeScript, with hidden tests.

The problem

There are n courses labelled 0…n-1. Each pair [a, b] in prereqs means you must take course b before course a. Return True if it is possible to finish all courses, or False if the prerequisites contain a cycle (a deadlock where nothing can start).

EXAMPLE 1
Input n = 2, prereqs = [[1, 0]]
Output True
take 0, then 1
EXAMPLE 2
Input n = 2, prereqs = [[1, 0], [0, 1]]
Output False
each needs the other first — a cycle
CONSTRAINTS
  • A schedule exists iff the prerequisite graph is a DAG (has no directed cycle).
  • Use a topological sort: Kahn’s algorithm (repeatedly remove a course with no remaining prerequisites) or DFS cycle detection.
  • If every course is eventually removable (all get scheduled), return True; if some remain stuck, there is a cycle.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement can_finish(n, prereqs): build the dependency graph and each course’s in-degree, start from the courses with in-degree 0, and repeatedly "take" a course, decrementing its dependents’ in-degrees. If you can take all n, return True; otherwise a cycle blocked you.

HINTS — 4 IDEAS
  1. Edge [a, b] means b → a (b unlocks a). Track each course’s in-degree = number of unmet prerequisites.
  2. Seed a queue with every course whose in-degree is 0 — those can be taken immediately.
  3. Take a course from the queue, count it, and decrement the in-degree of each course it unlocks; enqueue any that hit 0.
  4. If the number taken equals n, all courses were schedulable. If fewer, a cycle left some permanently blocked.
CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Algorithms & DSA