187. Course Schedule
Your university offers num_courses courses, labeled 0 through num_courses - 1. Some of them lock each other: a pair [a, b] in the list prerequisites means you have to pass course b before you may enroll in course a.
Your function receives the integer num_courses and the list of pairs prerequisites, and returns true if there is some order in which you can get through every course, or false if the requirements are impossible to satisfy.
The schedule breaks down exactly when some group of courses ends up requiring itself in a loop — so this is really a question about detecting a cycle in a directed graph.
Example 1:
Input: num_courses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: Course 1 needs course 0 first. Taking 0 then 1 clears everything, so the answer is true.
Example 2:
Input: num_courses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: Course 1 needs 0, but 0 also needs 1. Neither can ever be started, so the answer is false.
Example 3:
Input: num_courses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]]
Output: true
Explanation: The requirements form the straight chain 0 → 1 → 2 → 3, which you can walk front to back.
Constraints:
- 1 ≤ num_courses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- 0 ≤ a, b < num_courses
- A pair may repeat, and a pair may even name the same course twice (a course that requires itself can never be taken).
Hints:
Draw each pair [a, b] as a directed edge b → a ("finish b, then a unlocks"). The schedule is completable exactly when this graph has no directed cycle.
Count how many prerequisites each course still needs (its indegree). Any course with indegree 0 can be taken right now — take it, and lower the count of every course it unlocks. If this process stalls before all n courses are taken, a cycle is blocking you (Kahn's algorithm).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num_courses = 2, prerequisites = [[1, 0]]
Expected output: true