Back to Problems

Course Schedule

Medium
DFS

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1] indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Key Insight: This is a cycle detection problem in a directed graph!

  • Courses are nodes
  • Prerequisites are directed edges (bi -> ai)
  • If there's a cycle, some courses depend on each other circularly, making completion impossible

DFS for Cycle Detection: Use three states for each node:

  • UNVISITED (not yet explored)
  • VISITING (currently in DFS path - on the call stack)
  • VISITED (fully explored, no cycle through this node)

If we encounter a VISITING node while exploring, we found a cycle!

Example:

Course 0 depends on 1
Course 1 depends on 0
Graph: 0 <-> 1 (cycle!)

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0 first, then course 1. No cycle.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Course 1 requires course 0, and course 0 requires course 1. This is a cycle.

Constraints

  • •1 <= numCourses <= 2000
  • •0 <= prerequisites.length <= 5000
  • •prerequisites[i].length == 2
  • •0 <= ai, bi < numCourses
  • •All the pairs prerequisites[i] are unique.
Show Hints (4)
Hint 1: Model this as a directed graph where an edge from A to B means "A requires B".
Hint 2: The question becomes: does this directed graph have a cycle?
Hint 3: Use DFS with three states: unvisited, currently visiting (in DFS stack), and fully visited.
Hint 4: If you reach a node that is "currently visiting", you've found a back edge (cycle).
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?