noodleProblems/
Course Schedule II
#169

Course Schedule II

AlgorithmmediumDepth First SearchBreadth First SearchGraphTopological Sort

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 **an ordering** of all numCourses courses such that every prerequisite is satisfied (for each pair, b appears before a). If multiple valid orderings exist, return any one of them. If it is impossible to finish all courses — the prerequisite relation contains a **cycle** — return an empty array.

Example cases

  • linear chain
    in numCourses = 2prerequisites =
    10
    out [0,1]
    0 has no prerequisites, so it must come first; 1 needs 0.
  • diamond dependency
    in numCourses = 4prerequisites =
    10
    20
    31
    32
    out [0,1,2,3]
    0 unlocks both 1 and 2, and 3 needs both — any order with 0 first and 3 last works.
  • cycle is impossible
    in numCourses = 2prerequisites =
    10
    01
    out []
    0 needs 1 and 1 needs 0 — a cycle, so no ordering can satisfy both.

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]]