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 {
  private final int[] parent;
  private final int[] rank;
  private int count;
5 
  public UnionFind(int n) {
      parent = new int[n];
      rank = new int[n];
      count = n;
      for (int i = 0; i < n; i++) {
          parent[i] = i;
      }
  }
14 
  public int find(int x) {
      while (parent[x] != x) {
          parent[x] = parent[parent[x]]; // path compression
          x = parent[x];
      }
      return x;
  }
22 
  public boolean union(int a, int b) {
      int rootA = find(a);
      int rootB = find(b);
      if (rootA == rootB) {
          return false;
      }
      if (rank[rootA] < rank[rootB]) {
          parent[rootA] = rootB;
      } else if (rank[rootA] > rank[rootB]) {
          parent[rootB] = rootA;
      } else {
          parent[rootB] = rootA;
          rank[rootA]++;
      }
      count--;
      return true;
  }
40 
  public boolean connected(int a, int b) {
      return find(a) == find(b);
  }
44 
  public int count() {
      return count;
  }
48}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Representing each set by a root element lets you test membership by comparing roots.
2Path compression and union by rank together keep operations nearly constant time.
3Tracking a count field gives you the number of distinct groups for free.

Related explainers

java

@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter

Advanced 10 steps

java

package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern

Intermediate 5 steps

java

public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding

Intermediate 6 steps

java

public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io

Intermediate 8 steps

java

public final class EncodingDetector {
 
    public enum Encoding {
        UTF_8, UTF_16LE, UTF_16BE, UTF_32LE, UTF_32BE, ASCII, UNKNOWN

Detecting text encoding from raw bytes in Java

byte-manipulation encoding-detection bitwise-operations

Intermediate 8 steps

java

public final class ImportOrganizer {
 
    private static final Pattern IMPORT_LINE =
            Pattern.compile("^import\\s+(static\\s+)?([\\w.]+(?:\\.\\*)?)\\s*;\\s*$");