noodleProblems/
Course Schedule
#150

Course Schedule

AlgorithmmediumDepth First SearchBreadth First SearchGraph

There are numCourses courses labelled 0 to numCourses - 1. You are given a list prerequisites where prerequisites[i] = [a, b] means you must take course b **before** course a.

Return true if it is possible to finish all the courses, and false otherwise.

It is possible to finish exactly when the prerequisite relation contains **no cycle** — a cycle would mean a course is, transitively, its own prerequisite.

Example cases

  • two courses, one prerequisite
    in numCourses = 2prerequisites =
    10
    out true
    Take 0, then 1 — no cycle, so all courses can be finished.
  • mutual prerequisites
    in numCourses = 2prerequisites =
    10
    01
    out false
    0 needs 1 and 1 needs 0 — a cycle, so neither can ever be taken first.
  • no prerequisites
    in numCourses = 3, prerequisites = []
    out true

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a, b < numCourses
  • All the pairs prerequisites[i] are distinct.
Saved
numCourses =
2
prerequisites =
[[1,0]]