Course Schedule II

Kahn's algorithm — return pop order

Topological sort — output the ordering, not just detect cycles.

Published Apr 16, 2026

Problem

Given numCourses and a list of prerequisite pairs [a, b] ("take b before a"), return any valid course order. If no such order exists, return an empty array.

Input

numCourses = 2, prerequisites = [[1, 0]]

Output

[0, 1]

Input

numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Output

[0, 1, 2, 3] (or [0, 2, 1, 3])

Input

numCourses = 1, prerequisites = []

Output

[0]

Intuition

This is problem #207 with one extra requirement: record the pop order as Kahn's algorithm runs. Every time a node comes out of the queue, append it to the answer. If the cycle check fails (fewer than numCourses popped), return an empty list.

Multiple valid orders can exist — the problem accepts any of them. That means the harness can't compare equality against one fixed answer; it must verify that the returned order satisfies every prerequisite constraint.

Approach

Kahn's with order recording

TimeO(V+E)

SpaceO(V+E)

Recommended

Same structure as #207, but push into a result vector on each pop. If the result length isn't numCourses at the end, return an empty vector.

use std::collections::VecDeque;

impl Solution {
    pub fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
        let n = num_courses as usize;
        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
        let mut indeg: Vec<usize> = vec![0; n];
        for e in &prerequisites {
            let (a, b) = (e[0] as usize, e[1] as usize);
            adj[b].push(a);
            indeg[a] += 1;
        }
        let mut q: VecDeque<usize> = VecDeque::new();
        for i in 0..n {
            if indeg[i] == 0 {
                q.push_back(i);
            }
        }
        let mut order: Vec<i32> = Vec::with_capacity(n);
        while let Some(u) = q.pop_front() {
            order.push(u as i32);
            for &v in &adj[u] {
                indeg[v] -= 1;
                if indeg[v] == 0 {
                    q.push_back(v);
                }
            }
        }
        if order.len() == n {
            order
        } else {
            Vec::new()
        }
    }
}

Rust · runnable

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[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[] = [];
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    order.push(u);
    for (const v of adj[u]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

TypeScript · runnable

DFS postorder

TimeO(V+E)

SpaceO(V+E)

Alternative recipe: DFS from each unvisited node, push the node to the answer after its children are done. Reverse the answer at the end. Detect cycles with the three-color trick.

Conceptually cleaner on paper, but the recursion needs stack space and cycle detection needs another pass. Kahn's is usually the go-to.

impl Solution {
    pub fn find_order(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
        let n = num_courses as usize;
        let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
        for e in &prerequisites {
            adj[e[1] as usize].push(e[0] as usize);
        }
        let mut color = vec![0u8; n];
        let mut order: Vec<i32> = Vec::with_capacity(n);
        fn dfs(
            u: usize,
            adj: &[Vec<usize>],
            color: &mut [u8],
            order: &mut Vec<i32>,
        ) -> bool {
            color[u] = 1;
            for &v in &adj[u] {
                match color[v] {
                    1 => return false,
                    0 => {
                        if !dfs(v, adj, color, order) {
                            return false;
                        }
                    }
                    _ => {}
                }
            }
            color[u] = 2;
            order.push(u as i32);
            true
        }
        for u in 0..n {
            if color[u] == 0 && !dfs(u, &adj, &mut color, &mut order) {
                return Vec::new();
            }
        }
        order.reverse();
        order
    }
}

Rust · runnable

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const color = new Array(numCourses).fill(0);
  const order: number[] = [];
  const dfs = (u: number): boolean => {
    color[u] = 1;
    for (const v of adj[u]) {
      if (color[v] === 1) return false;
      if (color[v] === 0 && !dfs(v)) return false;
    }
    color[u] = 2;
    order.push(u);
    return true;
  };
  for (let u = 0; u < numCourses; u++) {
    if (color[u] === 0 && !dfs(u)) return [];
  }
  return order.reverse();
}

TypeScript · runnable

Trace

Kahn's on numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]:

step	queue	in-degrees	order
init	[0]	[0,1,1,2]	[]
1	[1,2]	[0,0,0,2]	[0]
2	[2,3]	[0,0,0,1]	[0,1]
3	[3]	[0,0,0,0]	[0,1,2]
4	[]	[0,0,0,0]	[0,1,2,3]

[0, 1, 2, 3] is one of two valid orders; [0, 2, 1, 3] is the other. Both satisfy "0 before 1 and 2, 1 and 2 before 3".

Edge cases

No prerequisites — return [0, 1, ..., n-1] (the order the queue starts in).
Cycle — return [].
Multiple valid answers — any valid one is accepted; deterministic output depends on queue iteration order.

Takeaway

The output of this problem is a witness to a topological order. In contests or code reviews, prefer tests that verify the witness is valid rather than that it matches one specific order — otherwise you'll reject perfectly correct answers that happen to use a different queue discipline.

Medium#207

Course Schedule

Cycle detection in directed graph. Both DFS (3-color) and Kahn’s BFS work.

Medium#133

Clone Graph

BFS/DFS with a visited HashMap that maps old → new nodes.

Hard#127

Word Ladder

BFS on an implicit graph. Each word is a node, edges connect words differing by one letter.