Module 4 · Topological Sort

Course Schedule

MediumProblem 11 of 25 9 min read ~20 min to solve LeetCode

GraphTopological SortBFSDFS

Asked atAmazonGoogleMicrosoftMetaApple

Problem Statement

There are numCourses courses labelled 0..numCourses - 1. You are given an array prerequisites where prerequisites[i] = [course, prerequisite] means you must take prerequisite before course.

Return true if it is possible to finish all courses, otherwise return false. In graph terms, courses are nodes and prerequisites are directed edges from prerequisite to course. You can finish all courses exactly when this directed graph has no cycle.

Input

An integer numCourses and a directed edge list prerequisites, where each pair [course, prerequisite] points from prerequisite to course.

Output

A boolean: true if every course can be completed, false if some cycle makes completion impossible.

Constraints

•1 <= numCourses <= 2000
•0 <= prerequisites.length <= 5000
•prerequisites[i].length == 2
•0 <= course, prerequisite < numCourses
•All prerequisite pairs are unique

Examples

Example 1

Input:

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

Output: true

Explanation: Take course 0 first, then course 1. The graph is 0 → 1, which is acyclic.

Example 2

Input:

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

Output: false

Explanation: Course 0 needs 1 and course 1 needs 0. Neither can be started, so the cycle blocks completion.

Example 3

Input:

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: true

Explanation: One valid plan is 0, then 1 and 2 in either order, then 3. There is no directed cycle.

Learning Objectives

Model prerequisites as a directed graph and connect feasibility to acyclicity.
Use Kahn's algorithm to repeatedly remove zero-indegree nodes and detect leftover cycle nodes.
Use DFS 3-color marking to recognise a back edge into the current recursion path.
Explain why topological-sort problems are about dependencies, not shortest paths or connected components.

Intuition

A course can be taken only after all incoming edges into it have been satisfied. So the clean mental model is: keep taking courses with zero remaining prerequisites. Each time you take one, it removes an outgoing edge from that course to every dependent course. If that makes another course's prerequisite count drop to zero, it becomes available next.

If the graph is a DAG, this peeling process eventually removes every node. If a cycle exists, every node in the cycle waits for another node in the same cycle, so none of them ever becomes zero-indegree. That is why the processed-count check is a cycle detector.

DFS gives the same answer from the opposite angle: while exploring a dependency chain, seeing a node already on the current recursion path means the chain loops back on itself. A finished node is safe; an in-progress node proves a cycle.

Common mistakes

×Reversing the edge direction. For [course, prerequisite], add prerequisite → course and increment indegree of course.
×Checking only whether the initial queue is empty. Some graphs start with zero-indegree nodes but still contain a separate cycle.
×Marking DFS nodes as fully processed before their descendants are complete, which hides back edges.
×Assuming the graph must be connected. Course graphs can have many independent components; scan every course.
×Returning true after processing one chain instead of verifying processed count equals numCourses.

Algorithm Explanation

Kahn's BFS:

Build adjacency lists from each prerequisite to the courses that depend on it.
Count indegree for every course.
Put all zero-indegree courses in a queue.
Pop a course, count it as processed, and decrement indegree for each dependent course. Any dependent course that reaches zero joins the queue.
If processed == numCourses, every node was peeled away, so no cycle exists; otherwise the leftover nodes are trapped in a cycle.

DFS 3-color:

Use 0 = unvisited, 1 = visiting, 2 = done.
Start DFS from every unvisited course.
Entering a node marks it visiting. Reaching another visiting node is a back edge and therefore a cycle.
After all descendants are safe, mark the node done. If no DFS finds a back edge, all courses can be finished.

Solutions

Solution 1: Kahn's algorithm (BFS indegrees)

When to prefer this:

Best default when you may also need a course ordering later. It exposes the available courses layer by layer and detects cycles by leftover unprocessed nodes.

Treat each zero-indegree course as immediately available. Remove available courses one by one, update the indegrees of dependent courses, and count how many courses were successfully removed.

Step-by-step

Allocate an adjacency list for every course.
For each [course, prerequisite], append course to prerequisite's outgoing list and increment indegree[course].
Enqueue every course with indegree 0.
Pop from the queue, increment processed, and relax outgoing edges by decrementing neighbours' indegrees.
Return processed == numCourses; a smaller count means a cycle kept some courses locked.

Time

O(V + E)

Space

O(V + E)

V is numCourses and E is prerequisites.length; adjacency, indegree, and queue dominate space.

Java implementation

Loading…

Solution 2: DFS 3-color cycle detection

When to prefer this:

Elegant when the question is only cycle detection. It avoids maintaining indegrees and expresses the invariant directly: a gray node on the call stack means a cycle.

Run DFS over the prerequisite graph with colors for unvisited, visiting, and done. A directed edge to a visiting node is a back edge, which makes finishing impossible.

Step-by-step

Build the same prerequisite → course adjacency list.
For each unvisited course, start DFS.
Mark the course visiting before exploring neighbours.
If any neighbour is visiting, return cycle found. If a neighbour is unvisited, recursively check it.
Mark the course done after all outgoing edges are safe.

Time

O(V + E)

Space

O(V + E)

Adjacency is O(V + E); color and recursion stack are O(V).

Java implementation

Loading…

Dry Run

Sample input

Kahn trace for numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Edges are 0 → 1, 0 → 2, 1 → 3, 2 → 3.

Step	Queue before pop	Popped	Indegrees after updates	Processed count
Init	[0]	-	[0,1,1,2]	0
1	[0]	0	[0,0,0,2]; enqueue 1 and 2	1
2	[1,2]	1	[0,0,0,1]	2
3	[2]	2	[0,0,0,0]; enqueue 3	3
4	[3]	3	[0,0,0,0]	4

All four courses are processed, so every dependency chain eventually unlocked. A cycle would leave at least one course unprocessed with positive indegree.

Interview Tips

Say the graph invariant first: finishing all courses is possible iff the prerequisite graph is a DAG. Then choose Kahn's algorithm as the practical default because it naturally produces a topological order and gives a clear cycle test. If asked for a lighter pure-cycle solution, pivot to DFS colors. Be precise with edge direction; most wrong solutions fail before the algorithm even starts.

Likely follow-ups

Return one valid course order instead of only true or false.
Return all courses involved in a cycle.
What if prerequisites are added one at a time and you must keep answering whether the plan is valid?
How would you schedule courses by semester when all currently available courses can be taken in parallel?

Key Takeaways

Prerequisite feasibility is directed cycle detection.
Kahn's algorithm removes zero-indegree nodes; leftover nodes imply a cycle.
DFS 3-color marking detects cycles when an edge points to a node still on the recursion stack.
Always build edges from prerequisite to course for this problem family.

Reusable template: Topological feasibility: build directed edges prereq → dependent, peel zero-indegree nodes, and verify every node was processed.

Problem Statement

Input

Output

Constraints

Examples

Learning Objectives

Intuition

Common mistakes

Algorithm Explanation

Solutions

Solution 1: Kahn's algorithm (BFS indegrees)

Step-by-step

Java implementation

Solution 2: DFS 3-color cycle detection

Step-by-step

Java implementation

Dry Run

Sample input

Interview Tips

Likely follow-ups

Similar Problems

Key Takeaways