Course Schedule

MediumGraphs / Topological SortTopological sort / directed-graph cycle detectiontopological-sortdfscycle-detection

Maintained by Vikas Dulgunde, software engineer

You have a set of courses numbered from 0 up to numCourses minus 1. Each entry in the prerequisites list is a pair [a, b] that says course b has to be done before course a. The pairs together describe which courses unlock which.

Your job is to report whether a full ordering of all the courses exists. That ordering is only possible when no course ends up, directly or through a chain, depending on itself.

If you picture each course as a point and each prerequisite as an arrow from the earlier course to the later one, the whole thing is a directed graph. Finishing every course is feasible exactly when that graph has no cycle.

Return true when all courses are reachable in some valid order, and false when a cycle makes that impossible.

Examples

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

Output: true

Course 0 has no prerequisite, so take it first, then course 1. Both finish, so the answer is true.

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

Output: false

Course 1 needs course 0 and course 0 needs course 1. Neither can start, which is a cycle, so the answer is false.

Input: numCourses = 5, prerequisites = [[1, 0], [2, 0], [3, 1], [4, 2]]

Output: true

Course 0 unlocks 1 and 2, which in turn unlock 3 and 4. The dependencies branch out without ever looping back, so all five courses complete.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
Each prerequisites[i] has exactly two entries, both valid course labels in [0, numCourses - 1]
No prerequisite pair is duplicated

Visible test cases

canFinish(2, [[1,0]]) == true
canFinish(2, [[1,0],[0,1]]) == false
canFinish(4, [[1,0],[2,1],[3,2]]) == true
canFinish(3, [[0,1],[1,2],[2,0]]) == false
canFinish(1, []) == true
canFinish(5, [[1,0],[2,0],[3,1],[4,2]]) == true

Hints

Hint 1

Model the courses as nodes and each pair [a, b] as a directed edge from b to a. The question becomes: does this directed graph contain a cycle?

Hint 2

A course with no remaining unmet prerequisites can be taken right away. Track how many prerequisites each course still has using an in-degree count.

Hint 3

Repeatedly take every course whose in-degree is 0, then reduce the in-degree of the courses it unlocks. If you manage to take all of them, there was no cycle.

Loading the editor...

Approaches

DFS cycle detection

Time O(V + E) where V is numCourses and E is the prerequisite count · Space O(V + E) for the adjacency list plus the recursion stack and state array

Walk the dependency graph with depth-first search and look for a node that appears again on the current path, which signals a cycle.

Build an adjacency list mapping each prerequisite to the courses that depend on it.
Give every node one of three states: unvisited, currently on the active path, or fully processed.
Run DFS from each unvisited node. Mark a node as on-path when you enter it and as processed when you leave it.
If DFS reaches a node already marked on-path, a cycle exists, so return false.
If every node finishes without that happening, return true.

Kahn topological sort (BFS)

Time O(V + E) · Space O(V + E) for the adjacency list, in-degree array, and queue

Peel off courses that have no outstanding prerequisites one layer at a time. If you can remove every course this way, the graph is acyclic.

Compute the in-degree of each course (how many prerequisites point at it) and build the adjacency list.
Seed a queue with every course whose in-degree is 0.
Pop a course, count it as taken, and decrement the in-degree of each course it unlocks; push any that drop to 0.
Continue until the queue empties.
Return true only if the number of courses taken equals numCourses; a leftover means a cycle trapped some courses.

Common mistakes

Reversing the edge direction. The pair is [course, prereq], so the arrow runs from prereq to course; flipping it produces a wrong in-degree count.
Forgetting that courses with no prerequisites still exist. An empty prerequisites list must return true, and isolated nodes must seed the queue.
In a plain DFS, marking a node as visited but never clearing the on-path flag, which can either miss a cycle or report a false one.
Comparing only against a global visited set instead of the active recursion path, so a node shared by two valid branches is mistaken for a cycle.

Follow-up variations

Return an actual valid order of courses instead of just a boolean (this is the Course Schedule II variant).
Report which courses are part of the cycle when one exists.
Handle the case where the same prerequisite pair can appear multiple times and edges carry weights.
Find the minimum number of semesters needed if you can take any number of unlocked courses in parallel each semester.

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

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

Output: true

Course 0 has no prerequisite, so take it first, then course 1. Both finish, so the answer is true.

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

Output: false

Course 1 needs course 0 and course 0 needs course 1. Neither can start, which is a cycle, so the answer is false.

Input: numCourses = 5, prerequisites = [[1, 0], [2, 0], [3, 1], [4, 2]]

Output: true

Course 0 unlocks 1 and 2, which in turn unlock 3 and 4. The dependencies branch out without ever looping back, so all five courses complete.

Hints

Hint 1

Model the courses as nodes and each pair [a, b] as a directed edge from b to a. The question becomes: does this directed graph contain a cycle?

Hint 2

A course with no remaining unmet prerequisites can be taken right away. Track how many prerequisites each course still has using an in-degree count.

Hint 3

Repeatedly take every course whose in-degree is 0, then reduce the in-degree of the courses it unlocks. If you manage to take all of them, there was no cycle.

Approaches

DFS cycle detection

Time O(V + E) where V is numCourses and E is the prerequisite count · Space O(V + E) for the adjacency list plus the recursion stack and state array

Walk the dependency graph with depth-first search and look for a node that appears again on the current path, which signals a cycle.

Build an adjacency list mapping each prerequisite to the courses that depend on it.
Give every node one of three states: unvisited, currently on the active path, or fully processed.
Run DFS from each unvisited node. Mark a node as on-path when you enter it and as processed when you leave it.
If DFS reaches a node already marked on-path, a cycle exists, so return false.
If every node finishes without that happening, return true.

Kahn topological sort (BFS)

Time O(V + E) · Space O(V + E) for the adjacency list, in-degree array, and queue

Peel off courses that have no outstanding prerequisites one layer at a time. If you can remove every course this way, the graph is acyclic.

Compute the in-degree of each course (how many prerequisites point at it) and build the adjacency list.
Seed a queue with every course whose in-degree is 0.
Pop a course, count it as taken, and decrement the in-degree of each course it unlocks; push any that drop to 0.
Continue until the queue empties.
Return true only if the number of courses taken equals numCourses; a leftover means a cycle trapped some courses.

Common mistakes

Reversing the edge direction. The pair is [course, prereq], so the arrow runs from prereq to course; flipping it produces a wrong in-degree count.

Forgetting that courses with no prerequisites still exist. An empty prerequisites list must return true, and isolated nodes must seed the queue.

In a plain DFS, marking a node as visited but never clearing the on-path flag, which can either miss a cycle or report a false one.

Comparing only against a global visited set instead of the active recursion path, so a node shared by two valid branches is mistaken for a cycle.

Follow-up variations

Return an actual valid order of courses instead of just a boolean (this is the Course Schedule II variant).

Report which courses are part of the cycle when one exists.

Handle the case where the same prerequisite pair can appear multiple times and edges carry weights.

Find the minimum number of semesters needed if you can take any number of unlocked courses in parallel each semester.

Course Schedule

Examples

Constraints

Hints

Approaches

DFS cycle detection

Kahn topological sort (BFS)

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Course Schedule

Examples

Constraints

Hints

Approaches

DFS cycle detection

Kahn topological sort (BFS)

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep