The problem. There are numCourses courses, numbered 0 to numCourses - 1. Each pair [course, pre] in prerequisites means you must take pre before course. Return true if you can finish every course.
numCourses = 2, prerequisites = [[1,0]] -> true (take 0, then 1)
numCourses = 2, prerequisites = [[1,0],[0,1]] -> false (each needs the other first)
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] -> trueWhenever a problem says prerequisites, dependencies, build order or A must come before B, draw an arrow from each thing to whatever depends on it. You get a directed graph, and the question becomes: can every vertex be lined up so that all arrows point forwards? Such a line-up is a topological order.
It exists exactly when the graph has no directed cycle. A cycle is a set of tasks that each wait for another one in the set, so none of them can ever go first.
Kahn's algorithm builds the order the way you'd plan a timetable. Count, for every vertex, how many arrows point into it — its in-degree, the prerequisites it still needs. Anything at 0 can be done now. Doing it removes its outgoing arrows, which may bring other vertices down to 0. Repeat. If you run out of ready vertices before everything is done, the leftovers are stuck behind a cycle.
Go through the courses again and again, taking any course whose prerequisites have all been taken. Stop when a full pass takes nothing new.
function canFinish(numCourses, prerequisites) { const taken = new Array(numCourses).fill(false); let count = 0; let progress = true; while (progress) { progress = false; for (let c = 0; c < numCourses; c++) { if (taken[c]) continue; // c is ready when every one of its prerequisites is already taken const ready = prerequisites.every(([course, pre]) => course !== c || taken[pre]); if (ready) { taken[c] = true; count++; progress = true; } } } return count === numCourses;}Time O(V² · E), space O(V). A pass checks every course against every prerequisite pair, and a long chain of courses needs up to V passes. The waste: each pass re-checks courses that are nowhere near ready.
Build the arrows once, and keep a count of what each course is still waiting for. A queue holds the courses that are ready. Taking a course lowers the count of every course it unlocks; one that reaches 0 joins the queue.
Courses start when their count of unfinished prerequisites hits 0. Try the cycle example.
function canFinish(numCourses, prerequisites) { const next = Array.from({ length: numCourses }, () => []); // course -> courses it unlocks const indegree = new Array(numCourses).fill(0); // prerequisites still to take for (const [course, pre] of prerequisites) { next[pre].push(course); indegree[course]++; } const queue = []; for (let c = 0; c < numCourses; c++) { if (indegree[c] === 0) queue.push(c); // nothing to wait for: ready now } let taken = 0; let head = 0; while (head < queue.length) { const c = queue[head++]; taken++; // take course c for (const d of next[c]) { indegree[d]--; // one prerequisite of d is done if (indegree[d] === 0) queue.push(d); // all of d's prerequisites are done: d is ready } } return taken === numCourses; // a course never taken is stuck on a cycle}Time O(V + E), space O(V + E). Each course enters the queue at most once, and each arrow lowers a count exactly once. The arrow lists take O(V + E).
A cycle check on its own also answers the question. In a directed graph, visited isn't enough: reaching a finished course a second way (two courses that share a prerequisite) is not a loop. So a DFS keeps three states — new, on the current path, done — and only an arrow back onto the current path is a cycle.
function canFinish(numCourses, prerequisites) { const next = Array.from({ length: numCourses }, () => []); for (const [course, pre] of prerequisites) next[pre].push(course); const state = new Array(numCourses).fill(0); // 0 = new, 1 = on the current path, 2 = done const hasCycle = (c) => { if (state[c] === 1) return true; // back onto the current path: a cycle if (state[c] === 2) return false; // already checked: no cycle from here state[c] = 1; for (const d of next[c]) { if (hasCycle(d)) return true; } state[c] = 2; return false; }; for (let c = 0; c < numCourses; c++) { if (hasCycle(c)) return false; } return true;}Time O(V + E), space O(V + E). A course is expanded once — after that it's done and returns at once. The recursion can be V calls deep on a long chain of prerequisites.
Kahn's and the three-state DFS are equally fast. Kahn's has no recursion and hands you the order directly, which the next lesson needs; the DFS is the classic way to find a cycle.
true.false.[0, 0] is a cycle of length one.