java 48 lines · 7 steps

How union-find with path compression works

A disjoint-set structure that tracks connected groups using union by rank and path compression for near-constant lookups.

Explained by highlit
Intermediate disjoint-set path-compression union-by-rank data-structures amortized-complexity
1public class UnionFind {
2 private final int[] parent;
3 private final int[] rank;
4 private int count;
5 
6 public UnionFind(int n) {
7 parent = new int[n];
8 rank = new int[n];
9 count = n;
10 for (int i = 0; i < n; i++) {
11 parent[i] = i;
12 }
13 }
14 
15 public int find(int x) {
16 while (parent[x] != x) {
17 parent[x] = parent[parent[x]]; // path compression
18 x = parent[x];
19 }
20 return x;
21 }
22 
23 public boolean union(int a, int b) {
24 int rootA = find(a);
25 int rootB = find(b);
26 if (rootA == rootB) {
27 return false;
28 }
29 if (rank[rootA] < rank[rootB]) {
30 parent[rootA] = rootB;
31 } else if (rank[rootA] > rank[rootB]) {
32 parent[rootB] = rootA;
33 } else {
34 parent[rootB] = rootA;
35 rank[rootA]++;
36 }
37 count--;
38 return true;
39 }
40 
41 public boolean connected(int a, int b) {
42 return find(a) == find(b);
43 }
44 
45 public int count() {
46 return count;
47 }
48}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Representing each set by a root element lets you test membership by comparing roots.
  2. 2Path compression and union by rank together keep operations nearly constant time.
  3. 3Tracking a count field gives you the number of distinct groups for free.

Related explainers

java 
public class ThumbnailProcessor {
 
    private static final int MAX_CONCURRENCY = 4;
 

Bounded parallel thumbnail rendering in Java

concurrency thread-pool futures
Intermediate 7 steps
java 
public class SortedListMerger {
 
    public static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];

Merging two sorted arrays in Java

two-pointers merging arrays
Beginner 6 steps
go 
package cache
 
import (
	"container/list"

Building a generic LRU cache in Go

lru-cache generics linked-list
Intermediate 8 steps
java 
import java.util.ArrayDeque;
import java.util.Deque;
 
public final class RollingAverage {

A rolling average over a sliding window

sliding-window running-sum deque
Intermediate 7 steps
java 
@Target({ElementType.FIELD, ElementType.PARAMETER})
@Retention(RetentionPolicy.RUNTIME)
@Constraint(validatedBy = StrongPasswordValidator.class)
@Documented

Building a custom @StrongPassword validator in Spring

bean-validation annotations regex
Intermediate 7 steps
java 
@Component
public class JwtAuthenticationFilter extends OncePerRequestFilter {
 
    private final JwtTokenProvider tokenProvider;

How a JWT auth filter works in Spring

authentication jwt servlet-filter
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

How union-find with path compression works — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code