8.3 Topological Sort

Demo: Course Schedule II — LC 210 (Medium — Amazon/Google High)

Statement (Demo): Given numCourses and prerequisites, return one valid order to take every course, or [] if impossible. Example: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] → [0,2,1,3] (or [0,1,2,3]) | ⚡ numCourses ≤ 2000

Approach: Count every node's indegree; queue the zeros. Pop, append to the order, and decrement each neighbour's indegree — enqueue it when it reaches 0. If the order is missing nodes at the end, there was a cycle.

function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    indegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) if (--indegree[v] === 0) queue.push(v);
  }
  return order.length === numCourses ? order : []; // cycle → []
}

Complexity: Time O(V + E), Space O(V + E)