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

Graphs: Topological Sort & Union-Find

Topological sort

A topological sort only makes sense on a directed, acyclic graph (a DAG), and it produces a linear ordering of nodes such that every directed edge u → v places u before v in the output. It's the natural model for "this must happen before that" dependency chains — course prerequisites, build steps, task scheduling.

function topologicalSort(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);

  for (const [from, to] of edges) {
    graph[from].push(to);
    indegree[to]++;
  }

  const queue = [];
  for (let i = 0; i < n; i++) {
    if (indegree[i] === 0) queue.push(i);   // no unmet prerequisites — safe to start here
  }

  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      indegree[next]--;                      // one prerequisite of "next" just got satisfied
      if (indegree[next] === 0) queue.push(next);
    }
  }

  return order.length === n ? order : null;  // fewer than n nodes emitted means a cycle exists
}

This is Kahn's algorithm, and it doubles as a cycle detector at no extra cost: if order.length ends up less than n, some nodes never reached indegree zero, which can only happen if they sit inside a cycle where every node in it is permanently waiting on another node in the same cycle.

Union-Find (disjoint set)

Union-find answers a narrower but very common question fast: "are these two nodes in the same connected group," and it's built for a graph whose edges arrive incrementally, where re-running a full BFS or DFS after every new edge would be wasteful.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);   // everyone starts as their own group
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);    // path compression: flatten as we go
    }
    return this.parent[x];
  }

  union(a, b) {
    const rootA = this.find(a), rootB = this.find(b);
    if (rootA === rootB) return false;    // already connected — this edge would form a cycle

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA]++;
    }
    return true;
  }
}

Path compression (every find call flattens the tree it walks) combined with union by rank keeps both operations effectively constant time — technically O(α(n)), the inverse Ackermann function, which grows so slowly that it's under 5 for any input size that could ever exist in practice. union returning false when two nodes are already connected is itself a cycle-detection trick worth remembering: it's exactly how Kruskal's minimum-spanning-tree algorithm and "find the redundant connection" style problems decide whether a new edge is safe to add or would close a cycle.

Reach for union-find specifically when the graph is being built up one edge at a time and you need repeated "are these connected" answers along the way; reach for a fresh BFS/DFS when you have the whole graph up front and just need one traversal's worth of an answer.

Practice this on Code Lab: Topological Sort and Union-Find