Course Schedule II

The problem

Implement `findOrder(numCourses, prerequisites)` where `prerequisites[i] = [a, b]` means course `b` must be taken before course `a`. Return a valid order to take all `numCourses` courses, or an empty array if no valid order exists.

`numCourses = 3, prerequisites = [[1,0]]` should return an ordering with `0` before `1` (e.g. `[0,1,2]`, any order respecting that constraint is accepted). `numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]` is a pure cycle, so it returns `[]`.

The approach

Same setup as `courseSchedule`: a forward adjacency list built from `prerequisites`, an `inDegree` array, and a queue seeded with every course whose `inDegree` is already `0`.

The one change is what happens per dequeue — `courseSchedule` only incremented a `visited` counter; this pushes the dequeued node into an `order` array instead. That's sufficient because a course can only reach `inDegree === 0` (and thus get queued) after every prerequisite it was waiting on has already been dequeued and pushed into `order` — so the array is built in an order that never places a course before something it depends on.

The cycle check is the same gap-detection as before, just checked against the collected list instead of a count: `order.length === numCourses ? order : []`. A course stuck in a cycle never reaches `inDegree === 0`, never gets queued, and so never makes it into `order` — leaving it short of `numCourses` exactly when a full ordering is impossible.

The solution

class Solution {
    /**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {number[]}
     */
    findOrder(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);
        }

        const order = [];
        while (q.length) {
            const node = q.shift();
            order.push(node);

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

        return order.length === numCourses ? order : [];
    }
}

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