Topological Sort: The Algorithm Behind Course Schedules and Dependency Ordering

At some point in your career, you've run into a dependency problem. Build step A before B. Load module X before Y. Install package P before Q. These problems share a structure: a directed graph where you need to order nodes such that all dependencies come first.

That's topological sort. And if you can't produce a valid ordering — because the dependencies form a cycle (A needs B, B needs C, C needs A) — the problem is unsolvable.

Both halves are worth understanding: how to detect cycles in a directed graph, and how to produce a valid topological order when no cycle exists. Course Schedule tests the first. Course Schedule II tests the second. Alien Dictionary takes it a level further. All three use the same underlying machinery.

Two Approaches, Same Result

DFS with three states: Mark each node as unvisited (0), currently visiting (1), or fully processed (2). A cycle is detected when DFS reaches a node currently on the active path (state 1).

Kahn's Algorithm (BFS / in-degree): Repeatedly remove nodes with no incoming edges. If you remove all nodes, it's a valid DAG. If you get stuck with nodes remaining, there's a cycle.

First: valid DAG, topological order exists (0 → 1 → 2 → 3 → 4 or similar). Second: cycle, impossible to order.

Building the Graph

Both approaches start the same way — build an adjacency list from the input:

const buildGraph = (numCourses, prerequisites) => {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[course].push(prereq); // course depends on prereq
  }
  return graph;
};

Problem 1: Course Schedule (LeetCode 207)

The problem: Given numCourses courses (labeled 0 to n-1) and a list of [course, prerequisite] pairs, can you finish all courses? Return true if yes, false if there's a cycle.

Brute Force: No Shortcut Exists

There's no shortcut here — you have to traverse the dependency graph. The question is which traversal method you prefer.

Approach 1: DFS Cycle Detection

// Time: O(V + E), Space: O(V + E)
const canFinish = (numCourses, prerequisites) => {
  const graph = buildGraph(numCourses, prerequisites);
  const state = new Array(numCourses).fill(0);
  // 0 = unvisited, 1 = visiting (on current DFS path), 2 = visited (safe)
 
  const dfs = (course) => {
    if (state[course] === 1) return false; // back edge = cycle
    if (state[course] === 2) return true;  // already confirmed no cycle here
 
    state[course] = 1; // mark as in-progress
 
    for (const prereq of graph[course]) {
      if (!dfs(prereq)) return false;
    }
 
    state[course] = 2; // all dependencies checked, no cycle
    return true;
  };
 
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
 
  return true;
};

The three states are what make this work for directed graphs specifically. State 1 (visiting) means "this node is on the current DFS call stack." If you reach it again while it's still on the stack, you found a back edge — that's a cycle. State 2 (visited) is a memoization: "I already confirmed this subtree is cycle-free, skip it."

Approach 2: Kahn's Algorithm (BFS)

// Time: O(V + E), Space: O(V + E)
const canFinishKahn = (numCourses, prerequisites) => {
  // For Kahn's: track what depends on each course (reverse direction)
  const dependents = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
 
  for (const [course, prereq] of prerequisites) {
    dependents[prereq].push(course); // prereq completion unlocks course
    inDegree[course]++;              // course needs one more prereq done
  }
 
  // Start with all courses that have no prerequisites
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
 
  let processed = 0;
 
  // An index pointer, not queue.shift() — see the note under the next listing
  let head = 0;
  while (head < queue.length) {
    const prereq = queue[head++];
    processed++;
 
    for (const course of dependents[prereq]) {
      inDegree[course]--;
      if (inDegree[course] === 0) queue.push(course); // all prereqs done
    }
  }
 
  return processed === numCourses; // if stuck, cycle exists
};

If a cycle exists, the nodes in that cycle will never reach inDegree === 0 — they'll wait forever for a prerequisite that itself is waiting. processed stays below numCourses. That's your cycle signal.

Problem 2: Course Schedule II (LeetCode 210)

The problem: Same setup, but return the actual ordering of courses to take. Return an empty array if there's a cycle.

The logic is identical — you just need to record the order in which nodes get processed.

DFS Solution (Post-Order)

// Time: O(V + E), Space: O(V + E)
const findOrder = (numCourses, prerequisites) => {
  const graph = buildGraph(numCourses, prerequisites);
  const state = new Array(numCourses).fill(0);
  const order = [];
 
  const dfs = (course) => {
    if (state[course] === 1) return false; // cycle
    if (state[course] === 2) return true;  // already processed
 
    state[course] = 1;
 
    for (const prereq of graph[course]) {
      if (!dfs(prereq)) return false;
    }
 
    state[course] = 2;
    order.push(course); // add AFTER all dependencies are processed
    return true;
  };
 
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return [];
  }
 
  return order; // already in valid topological order
};

Adding the course to order in post-order (after recursing into all its prerequisites) naturally produces a valid topological ordering. Prerequisites end up earlier in the array than the courses that need them.

Kahn's Solution

// Time: O(V + E), Space: O(V + E)
const findOrderKahn = (numCourses, prerequisites) => {
  const dependents = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
 
  for (const [course, prereq] of prerequisites) {
    dependents[prereq].push(course);
    inDegree[course]++;
  }
 
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
 
  const order = [];
 
  let head = 0;
  while (head < queue.length) {
    const course = queue[head++];
    order.push(course); // add as we process it
 
    for (const dependent of dependents[course]) {
      inDegree[dependent]--;
      if (inDegree[dependent] === 0) queue.push(dependent);
    }
  }
 
  return order.length === numCourses ? order : [];
};

Kahn's builds the order naturally — nodes with no dependencies first, then nodes whose dependencies are now cleared. The check order.length === numCourses is the cycle detector.

Problem 3: Alien Dictionary (LeetCode 269)

The problem: Given a list of words sorted according to an alien language's alphabet, determine that alphabet's character ordering. Return an empty string if no consistent ordering exists — either because the constraints form a cycle, or because the input itself isn't validly sorted. If several orderings are consistent with the input, any one of them is accepted; the constraints only pin down what the adjacent-word comparisons reveal.

This is topological sort on character ordering derived from comparing adjacent words.

Deriving the Character Graph

// Time: O(C) where C = total characters across all words
// Space: O(U + min(U^2, N)) where U = unique chars, N = number of words
const alienOrder = (words) => {
  // Initialize graph for every unique character
  const graph = {};
  for (const word of words) {
    for (const char of word) {
      if (!graph[char]) graph[char] = new Set();
    }
  }
 
  // Compare adjacent words to derive ordering constraints
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i];
    const w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);
 
    // Invalid input: longer word comes before its prefix
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
 
    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        graph[w1[j]].add(w2[j]); // w1[j] comes before w2[j] in the alien alphabet
        break; // only the FIRST difference tells us the ordering
      }
    }
  }
 
  // Topological sort with DFS
  const state = {};
  const result = [];
 
  const dfs = (char) => {
    if (state[char] === 'visiting') return false; // cycle
    if (state[char] === 'visited') return true;
 
    state[char] = 'visiting';
 
    for (const neighbor of graph[char]) {
      if (!dfs(neighbor)) return false;
    }
 
    state[char] = 'visited';
    result.push(char);
    return true;
  };
 
  for (const char of Object.keys(graph)) {
    if (!dfs(char)) return '';
  }
 
  return result.reverse().join('');
};

Walking Through the Logic

Say the input is ["wrt", "wrf", "er", "ett", "rftt"]. Comparing adjacent words:

• "wrt" vs "wrf": t comes before f
• "wrf" vs "er": w comes before e
• "er" vs "ett": r comes before t
• "ett" vs "rftt": e comes before r

Graph edges: t → f, w → e, r → t, e → r. Topological order: w → e → r → t → f.

The key discipline: only the first differing character between two words gives you an ordering constraint. The characters after the first difference tell you nothing about ordering.

DFS vs Kahn's: Which to Pick in an Interview?

In practice, Kahn's is easier to explain verbally. DFS is what most people reach for instinctively. Know both, implement whichever comes more naturally under pressure.

Interview Tips

State the graph model first — and state which way your edges point. "Each course is a node. Each prerequisite relationship is a directed edge. I need to check if this directed graph contains a cycle." Then be explicit about the direction, because the two solutions above deliberately use opposite ones and mixing them up is the single most common way to write a topological sort that silently returns a reversed order:

• buildGraph (used by the DFS solutions) points course → prerequisite. buildGraph(2, [[1, 0]]) returns [[], [0]] — graph[1] holds 0, so the edge runs from course 1 to its prerequisite 0. The DFS recurses into prerequisites, so post-order emits prerequisites first and order needs no reversal.
• Kahn's dependents points the other way, prerequisite → course. Same input gives [[1], []]. That's the direction in-degree counting needs: inDegree[course] is "how many prerequisites are still outstanding."

Neither direction is the correct one in the abstract. What matters is that the direction you build matches the traversal you then write. Say out loud which one you've picked.

Three states vs two: Emphasize that directed graph cycle detection needs three states, not two. "In an undirected graph, revisiting any node signals a cycle. In a directed graph, it only signals a cycle if the node is on my current DFS path." This distinction shows depth.

Alien Dictionary pitfalls to call out:

1. Prefix edge case (longer word before its own prefix)
2. Only taking the first differing character between adjacent words
3. Reversing the DFS result (or building the graph in reverse to avoid the reverse)

Complexity: Both DFS and Kahn's run in O(V + E). V is courses/characters, E is prerequisites/ordering edges. Everything is visited exactly once. For Alien Dictionary, C (total characters in all words) bounds the work — you don't need to explicitly multiply words × word length.

When an interviewer asks "can you optimize further?", the honest answer has two halves, and only the first one is the one people give.

The asymptotic half: no. You have to look at every node and every edge at least once to know whether a cycle exists, so O(V + E) is a lower bound for this problem, and both solutions meet it. Say that.

The other half: your implementation may not actually be O(V + E) even when your comment says it is. queue.shift() in Kahn's is the example — same algorithm, same annotation, quadratic in practice, 2.2 seconds at V=160,000 where the one-line index-pointer fix takes 8 milliseconds. So the useful thing to reach for when asked to optimize further isn't a better algorithm, it's a re-read of your own code looking for an O(n) operation hiding inside an O(1)-shaped call. shift()/unshift()/splice(0, …) on a hot path, string concatenation in a loop, indexOf inside a nested loop where a Set belongs. That answer lands much better than "it's already optimal," and unlike that one it's usually true.