Coding Interview Patterns

Union-Find Applications

Beyond powering Kruskal's MST, union-find is the go-to structure for any "are these two things connected" question that arrives as a stream of incremental unions rather than a fixed graph to traverse once.

Number of connected components / number of islands: map grid cells to graph nodes, union adjacent land cells, count remaining roots
Cycle detection while building a graph edge-by-edge: a union that fails (both endpoints already share a root) means the new edge closes a cycle
"Accounts merge" / equivalence-class problems: union whenever two items are declared equivalent, then group by final root
With path compression and union by rank/size, both find and union run in amortized nearly-O(1) time — technically O(α(n)), the inverse Ackermann function, for all practical n indistinguishable from a constant — see Amortized Analysis
Beats repeated BFS/DFS whenever queries ("are u and v connected right now?") are interleaved with edge additions, since re-running a full traversal after every edge would be far more expensive

Union-Find with path compression and union by rank

class UnionFind {
    private final int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;                          // already connected — would form a cycle
        if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }
}