← DSA Atlas
Dedicated problem page · #207

Course Schedule

MediumTopological SortCycle detection by peeling zero in-degree nodesTopological sort (Kahn's BFS)
Solve on LeetCode ↗
207
MediumTopological SortTopological sort (Kahn's BFS)Cycle detection by peeling zero in-degree nodes

Course Schedule

There are numCourses courses labeled 0..numCourses-1. Given a list prerequisites where [a, b] means you must take course b before course a, decide whether you can finish all courses. This is possible exactly when the prerequisite graph has no cycle.

Open official problem prompt ↗
In plain English

Decide whether a set of ordering constraints is mutually satisfiable, i.e. whether the dependency graph can be linearized with no course depending (directly or transitively) on itself.

Picture it like this

Think of assembling furniture: each step lists what must already be built. If two steps each secretly require the other, you can never start; otherwise you can always find some step whose prerequisites are all done.

Example
Input
numCourses = 2, prerequisites = [[1, 0]]
Output
true
Why
Take course 0 first, then course 1; there is no circular dependency.
Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a_i, b_i < numCoursesAll prerequisite pairs are distinct
Pattern lesson

See the pattern, then code

Cycle detection by peeling zero in-degree nodes
Recognition clue

Pairwise 'must come before' constraints over labeled items is a dependency graph, and 'can it all be done' means 'is the directed graph acyclic'.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. A course with no remaining prerequisites can be taken now; taking it removes it as a prerequisite for others. If you can keep finding such courses until none are left, there was no cycle.

New words, made simpleKnow these before the algorithm
In-degree
How many prerequisites a course still has unmet.
Directed acyclic graph (DAG)
A directed graph with no cycles; exactly the graphs that admit a valid course order.
Topological order
A linear ordering of nodes where every edge points forward.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force permutation check

Factorial blowup; hopeless past a handful of courses.

Try every ordering of courses and verify all prerequisites are respected.

Time O(n! * E)Space O(n)
Best choiceKahn's algorithm (BFS topological sort)

Linear and directly reports cyclicity via the processed count.

Repeatedly remove courses with zero unmet prerequisites; a cycle exists iff some course is never removed.

Time O(V + E)Space O(V + E)
The rule we keep true

Invariant

Every course placed into the queue has all of its prerequisites already processed, so the queue only ever holds currently-takeable courses.

Why this is correct

Reasoning

In a DAG at least one node always has in-degree 0, so the peeling never stalls until all nodes are removed. If a cycle exists, none of its nodes can ever reach in-degree 0, so the processed count stays below numCourses and we return false.

The algorithm in three movesSay these aloud before coding
1Build a directed graph pre -> course and count in-degrees (number of unmet prerequisites)

indeg = [0, 1]

2Seed a queue with every course whose in-degree is 0

queue = [0] -> pop 0, indeg[1] -> 0

3Pop a course, mark it done, and decrement the in-degree of its dependents, enqueuing any that reach 0

processed = 2 == numCourses -> true

4Return true only if the number of courses processed equals numCourses

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
c0(0)0
c1(1)1
1 · Read[[1, 0]]
2 · AskWhat is each course's in-degree?
3 · Update stategraph: 0 -> [1]; indeg = [0, 1]
4 · ResultCourse 0 has no prerequisite.
Key takeaway

Course 0 has in-degree 0 and unlocks course 1, so both are processed.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-8Build adjacency list and in-degree array

    Edge pre -> course means finishing pre reduces course's unmet count.

  2. 2
    Lines 9-10Seed the frontier

    Courses with no prerequisites can be taken first.

  3. 3
    Lines 11-18Peel layer by layer

    Each removal may free dependents; count how many we manage to finish.

  4. 4
    Lines 19Cycle test

    If some course was never freed, a cycle blocked it and we return false.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No prerequisites at all (empty list) -> trivially true
  • A single self-dependency such as [[0, 0]] forms a cycle -> false
  • Disconnected components each handled independently
  • Duplicate-free but chained prerequisites forming a long path -> still true
!

Common beginner mistakes

  • Reversing the edge direction (treating [a, b] as a -> b instead of b -> a)
  • Returning true by default without checking that every node was processed
  • Using recursion-based DFS without a proper visiting/visited coloring, which mislabels cross edges as cycles
Check your understanding

Why is comparing the processed count to numCourses enough to detect a cycle?

More in Topological Sort

#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#1203Sort Items by Groups Respecting DependenciesTwo-level topological sort (order groups, then items within groups)#2050Parallel Courses IIITopological longest path (critical path)