Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtopological-sort

Course Schedule II

Problem (restated)

numCourses and prerequisites [a,b] (b before a). Return any valid order, or empty if cycle.

Intuition

Same as Course Schedule: Kahn indegree BFS; emit order; if count is less than n, cycle.

Approaches

Kahn's BFS topo

Unverified

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

Idea. build graph+indegree; queue zeros; pop and reduce neighbors.

Walkthrough. 2, [[1,0]] → [0,1]; cycle → [].

Trade-offs. DFS color topo also works; Kahn is template default.

Solution

export function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

export function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const g: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    g[b!]!.push(a!);
    indeg[a!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) {
      if (--indeg[v]! === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

Template connection

Topological sort prerequisites.

Reflection

The Kahn order is one valid course order. If a cycle lets fewer than n nodes leave, the answer is empty.
Several courses at indegree 0: queue order changes the output, and every such order is valid.
No prerequisites: any order of the courses is fine. One course is that course.