Topological Sort: Kahn's Algorithm and DFS in Python and TypeScript

The Problem

You have n courses numbered 0 to n − 1 and a list of prerequisite pairs. A pair [a, b] means you must finish course b before course a. Return an order in which you can take every course, or an empty list if it is impossible because the prerequisites form a cycle.

This is topological sorting in disguise: courses are nodes, each pair is a directed edge from b to a, and a valid order exists only if the graph has no cycle (it is a DAG, a directed acyclic graph).

Example 1

Input: n = 4, [[1, 0], [2, 0], [3, 1], [3, 2]]. Output: [0, 1, 2, 3]. Course 0 has no prerequisites, courses 1 and 2 need 0, and course 3 needs both 1 and 2. [0, 2, 1, 3] is also correct: there is often more than one valid order.

Example 2

Input: n = 2, [[0, 1], [1, 0]]. Output: []. Each course needs the other first, which is a cycle, so no order works.

Assumptions to confirm

• Is any valid order accepted, or a specific one, such as the smallest number first?
• Can there be duplicate pairs or courses with no prerequisites at all? The solutions handle both.
• Should a cycle return an empty list, raise an error, or just return false? This is the "can you finish all courses" variant.

The Naive Approach

The obvious approach is to repeatedly scan all courses for one whose prerequisites are all taken, take it, and repeat. Each scan is O(V + E) and you do up to V scans, so it is O(V × (V + E)). It is a fine starting point to say out loud, because the optimal version is the same idea with bookkeeping: instead of rescanning, keep a count of remaining prerequisites per course and a queue of courses that are ready.

The Optimal Approach: Kahn's Algorithm

Python and TypeScript Solutions

Kahn's algorithm in Python

from collections import deque


def course_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Kahn's algorithm. [a, b] means 'take b before a'. Returns [] if there is a cycle."""
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, before in prerequisites:
        graph[before].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == num_courses else []

Kahn's algorithm in TypeScript

The queue uses a moving head index instead of shift(), which is O(n) on JavaScript arrays and would quietly make the whole algorithm quadratic.

// Kahn's algorithm. [a, b] means "take b before a". Returns [] if there is a cycle.
function courseOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const indegree = new Array<number>(numCourses).fill(0);
  for (const [course, before] of prerequisites) {
    graph[before].push(course);
    indegree[course]++;
  }

  const queue: number[] = [];
  for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);

  const order: number[] = [];
  for (let head = 0; head < queue.length; head++) { // index pointer instead of shift(): O(1)
    const node = queue[head];
    order.push(node);
    for (const next of graph[node]) {
      if (--indegree[next] === 0) queue.push(next);
    }
  }
  return order.length === numCourses ? order : [];
}

The DFS approach

Depth-first search gives a second valid answer. Each node is marked as unvisited, on the current path, or done. Meeting a node that is still on the current path means you found a cycle. A node is added to the list only after everything that depends on it is finished, so reversing that list gives a topological order.

def course_order_dfs(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """DFS with three colours: 0 unvisited, 1 on the current path, 2 done."""
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for course, before in prerequisites:
        graph[before].append(course)

    state = [0] * num_courses
    post_order: list[int] = []

    def visit(node: int) -> bool:
        if state[node] == 1:
            return False              # back edge: a cycle
        if state[node] == 2:
            return True
        state[node] = 1
        for nxt in graph[node]:
            if not visit(nxt):
                return False
        state[node] = 2
        post_order.append(node)       # added after everything that depends on it
        return True

    for c in range(num_courses):
        if not visit(c):
            return []
    return post_order[::-1]

// DFS with three states: 0 unvisited, 1 on the current path, 2 done.
function courseOrderDfs(numCourses: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, before] of prerequisites) graph[before].push(course);

  const state = new Array<number>(numCourses).fill(0);
  const postOrder: number[] = [];

  const visit = (node: number): boolean => {
    if (state[node] === 1) return false; // back edge: a cycle
    if (state[node] === 2) return true;
    state[node] = 1;
    for (const next of graph[node]) if (!visit(next)) return false;
    state[node] = 2;
    postOrder.push(node); // added after everything that depends on it
    return true;
  };

  for (let c = 0; c < numCourses; c++) if (!visit(c)) return [];
  return postOrder.reverse();
}

The DFS version is recursive, so a graph with a very long chain can hit the recursion limit, especially in Python. That is a good reason to lead with Kahn's algorithm in an interview.

Kahn's Algorithm vs DFS

How to Talk Through It in an Interview

1. Clarify: "Pair [a, b] means b comes before a? Any valid order is fine? A cycle returns an empty list?"
2. Model it: "Courses are nodes and prerequisites are directed edges. I need a topological order, which exists only if there is no cycle."
3. Naive: "I could keep rescanning for a course with nothing left to wait for, but that is O(V × (V + E))."
4. Optimise: "Kahn's algorithm tracks in-degrees and a queue of ready courses, so each node and edge is handled once: O(V + E)."
5. Test: the four-course example, the two-course cycle, a graph with no edges and a single course.

Edge Cases and Follow-Ups

Practise It in a Mock Coding Round

Reading a solution is not the same as producing it with someone watching. In a real round you have to clarify the problem, say the brute force out loud, and keep talking while you type. MockIF runs coding rounds with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, follows up on edge cases and complexity, then scores the round and gives you specific feedback. A session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing). Read more about how a mock coding interview works.

Frequently Asked Questions