mafeshsho8lmafeshsho8l
Get Started
All coding questions

Course Schedule

medium
Blind 75NeetCode 150graphstopological-sortdfs

Problem

Given a number of courses and a list of prerequisite pairs, decide whether you can finish all courses. You can finish them only if the prerequisite relationships contain no cycle.

Examples

Input: 2 courses, prerequisites [[1, 0]]
Output: true
Take course 0 then course 1.
Input: 2 courses, prerequisites [[1, 0], [0, 1]]
Output: false
The two courses depend on each other circularly.

Constraints

  • • 1 <= numCourses <= 2000
  • • 0 <= prerequisites.length <= 5000
  • • Pairs may repeat
Hints(tap to reveal)
  • 1. Model courses as a directed graph.
  • 2. A valid schedule exists exactly when there is no cycle.
Optimal approach(spoiler)
  1. Build a directed graph and in-degree count from the prerequisites.
  2. Use Kahn's algorithm: queue all zero in-degree nodes.
  3. Repeatedly remove a node and decrement its neighbours' in-degrees.
  4. If every node gets processed, there is no cycle and the schedule is possible.
  5. O(V + E) time, O(V + E) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor