Course Schedule

The problem

Implement `canFinish(numCourses, prerequisites)` where `prerequisites[i] = [a, b]` means course `b` must be taken before course `a`. Return whether all `numCourses` courses, labelled `0` to `numCourses - 1`, can be completed.

A valid completion order exists exactly when the prerequisite graph has no cycle — if some course is (transitively) its own prerequisite, no ordering can satisfy every edge, so the scheduling question is really cycle detection over a directed graph.

The approach

Two structures come out of one pass over `prerequisites`: a forward adjacency list (`adj[prereq]` lists every course that prereq unlocks) and an `inDegree` array counting how many prerequisites each course still owes. Every other BFS in this log seeded its queue from a property already sitting on the cell — border, rotten, treasure; here the seed has to be computed first, since 'has no unmet prerequisites' doesn't exist until the edge list has been walked.

The queue starts with every course whose `inDegree` is already `0` — courses safe to take right now. Draining a course counts it as `visited` and decrements `inDegree` for everything it unlocks; a course only joins the queue once its own `inDegree` hits zero, meaning every prerequisite it was waiting on has already been processed.

`visited` tallies how many courses ever got dequeued. In a DAG, every course eventually has all its prerequisites processed and its `inDegree` drops to zero, so `visited` reaches `numCourses`. A course stuck in a cycle depends (transitively) on itself, so its `inDegree` never reaches zero and it's never queued — the cycle shows up as a gap between `visited` and `numCourses`, not as an explicit check.

The solution

class Solution {
    /**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {boolean}
     */
    canFinish(numCourses, prerequisites) {
        const adj = Array.from({ length: numCourses }, () => []);
        const inDegree = new Array(numCourses).fill(0);

        for (const [course, prereq] of prerequisites) {
            adj[prereq].push(course);
            inDegree[course]++;
        }

        const q = [];
        for (let i = 0; i < numCourses; i++) {
            if (inDegree[i] === 0) q.push(i);
        }

        let visited = 0;
        while (q.length) {
            const node = q.shift();
            visited++;

            for (const next of adj[node]) {
                inDegree[next]--;
                if (inDegree[next] === 0) q.push(next);
            }
        }

        return visited === numCourses;
    }
}

Time O(V + E)Space O(V + E)