Skip to main content
Ace Hired
All coding problems

Course Schedule

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

Maintained by Vikas D, 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.

  1. Build an adjacency list mapping each prerequisite to the courses that depend on it.
  2. Give every node one of three states: unvisited, currently on the active path, or fully processed.
  3. Run DFS from each unvisited node. Mark a node as on-path when you enter it and as processed when you leave it.
  4. If DFS reaches a node already marked on-path, a cycle exists, so return false.
  5. 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.

  1. Compute the in-degree of each course (how many prerequisites point at it) and build the adjacency list.
  2. Seed a queue with every course whose in-degree is 0.
  3. Pop a course, count it as taken, and decrement the in-degree of each course it unlocks; push any that drop to 0.
  4. Continue until the queue empties.
  5. 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.

Recommended problems

Build the rest of your prep