Course Schedule
MediumGraphs
There are numCourses courses, numbered 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must finish course b before you can take course a.
Return true if there is an order in which you can finish every course, and false if there is not.
Examples
Input: numCourses = 3, prerequisites = [[1, 0], [2, 1]] Output: true
Take course 0, then 1, then 2.
Input: numCourses = 3, prerequisites = [[0, 1], [1, 2], [2, 0]] Output: false
Course 0 waits for 1, 1 waits for 2 and 2 waits for 0, so none of them can start.
Constraints
1 ≤ numCourses ≤ 20000 ≤ prerequisites.length ≤ 50000 ≤ a, b < numCourses- No pair appears twice.
Stuck?
Hint 1
Draw each course as a node and each prerequisite as an arrow from b to a. You can finish everything exactly when the arrows never loop back on themselves.
Hint 2
Count each course’s unfinished prerequisites. Take the courses at zero, and each one you take lowers the count of the courses it unlocks (Kahn’s algorithm). If you take all of them, return true.
The idea
You can finish every course exactly when the prerequisites contain no loop. Take any course with nothing left to wait for and count it as done, since that may free the courses that needed it. Courses on a loop keep waiting on each other and are never taken, so the answer is whether every course got taken.
Time O(n + p) for n courses and p prerequisitesExtra space O(n + p)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
unlocks[b] lists the courses that course b is a prerequisite for. waiting[c] counts the prerequisites of course c that are not done yet.
function canFinish(numCourses, prerequisites) { const unlocks = Array.from({ length: numCourses }, () => []); const waiting = new Array(numCourses).fill(0); for (const [course, before] of prerequisites) { unlocks[before].push(course); waiting[course]++; } const ready = []; for (let c = 0; c < numCourses; c++) { if (waiting[c] === 0) ready.push(c); } let taken = 0; while (ready.length) { const course = ready.pop(); taken++; for (const next of unlocks[course]) { waiting[next]--; if (waiting[next] === 0) ready.push(next); } } return taken === numCourses;}The trap
This version walks from each course with one visited set and calls any course it meets a second time a loop. A loop does lead back to a course already seen, which is why it looks right. But a course can also be met twice without any loop. A course with two prerequisites is reached from each of them, and a course the outer loop already handled is met again from a prerequisite visited later. Those lists have a valid order and still get false. Telling the courses on the current path apart from the ones already finished fixes it.
function canFinish(numCourses, prerequisites) { const unlocks = Array.from({ length: numCourses }, () => []); for (const [course, before] of prerequisites) unlocks[before].push(course); const visited = new Set(); const dfs = (course) => { if (visited.has(course)) return false; // any course seen before counts as a cycle, even one finished on another path visited.add(course); return unlocks[course].every((next) => dfs(next)); }; for (let c = 0; c < numCourses; c++) { if (!visited.has(c) && !dfs(c)) return false; } return true;}