DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 10 of 16 · ~4 min

Graphs: Topological Sort & Union-Find

Topological sort

Everything the prerequisite system has been building toward. A topological sort is only defined on a directed, acyclic graph, and it produces an ordering where every edge before → after places before earlier in the output — precisely what a prerequisite means.

function suggestedCourseOrder(courseCount, prereqEdges) {   // edge [a, b]: a must precede b
  const graph = Array.from({ length: courseCount }, () => []);
  const indegree = new Array(courseCount).fill(0);

  for (const [before, after] of prereqEdges) {
    graph[before].push(after);
    indegree[after]++;
  }

  const queue = [];
  for (let i = 0; i < courseCount; i++) {
    if (indegree[i] === 0) queue.push(i);   // nothing left unmet — safe to schedule first
  }

  const order = [];
  while (queue.length) {
    const course = queue.shift();
    order.push(course);
    for (const next of graph[course]) {
      indegree[next]--;                      // one of next's prerequisites just cleared
      if (indegree[next] === 0) queue.push(next);
    }
  }

  return order.length === courseCount ? order : null;   // short output means the data is broken
}

This is Kahn's algorithm, O(V + E) — every node is queued and dequeued exactly once, every edge inspected exactly once, when its source is processed.

A precision worth having ready, because the casual version of it overreaches slightly. The usual line is "if the output comes up short, the leftover nodes are in a cycle." Some of them are — but not necessarily all of them. A node can also get stuck simply by depending, even indirectly, on something that's in a cycle, without belonging to the cycle itself. Say courses C and D require each other by mistake — a genuine cycle — and E requires D. E never reaches indegree zero either, but E isn't part of the cycle; it's just permanently waiting on something that is. The accurate statement: a short output proves the graph contains at least one cycle, and every course left out is either inside that cycle or reachable only through it. For the registrar the practical response is identical either way — a prerequisite rule needs a human to fix it — but the more careful version is worth having if an interviewer asks exactly why a particular node got dropped.

Union-Find (disjoint set)

A narrower, faster question: are these two things in the same group? This tool is built for the case where the graph doesn't exist all at once — edges trickle in one at a time, which is exactly how equivalency rulings really arrive, as individual petitions the registrar signs off on one by one. Re-running a full traversal after each single approval would be wasted motion.

class EquivalencyUnionFind {
  constructor(courseCodes) {
    this.parent = new Map(courseCodes.map((c) => [c, c]));   // everyone starts in their own group
    this.rank = new Map(courseCodes.map((c) => [c, 0]));
  }

  find(code) {
    if (this.parent.get(code) !== code) {
      this.parent.set(code, this.find(this.parent.get(code)));   // path compression as we go
    }
    return this.parent.get(code);
  }

  union(a, b) {
    const rootA = this.find(a), rootB = this.find(b);
    if (rootA === rootB) return false;    // already linked — this petition adds nothing

    if (this.rank.get(rootA) < this.rank.get(rootB)) {
      this.parent.set(rootA, rootB);
    } else if (this.rank.get(rootA) > this.rank.get(rootB)) {
      this.parent.set(rootB, rootA);
    } else {
      this.parent.set(rootB, rootA);
      this.rank.set(rootA, this.rank.get(rootA) + 1);
    }
    return true;
  }
}

const uf = new EquivalencyUnionFind(['STAT200', 'MATH250', 'MATH255']);
uf.union('STAT200', 'MATH250');
uf.union('MATH250', 'MATH255');
uf.find('STAT200') === uf.find('MATH255');   // true — linked transitively, no direct ruling needed

find flattens a little bit of the tree every time it walks one, and once union-by-rank is layered on top, both operations stop growing with the input in any way that matters in practice — the honest bound is O(α(n)), α being the inverse Ackermann function, and that function grows so slowly that it never exceeds 4 or 5 for any n you could actually construct. There's a free cycle check hiding in union too: when it returns false, that's the union-find structure telling you the new edge would only restate a connection that already existed, not create one.

Reach for union-find when rulings show up one at a time and "are these connected?" keeps getting asked in between. Reach for a plain BFS or DFS sweep instead when the entire graph is already assembled and a single pass over it will settle the question completely.

Topological Sort and Union-Find on Code Lab.