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

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion

Intermediate 8 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

package scheduler
 
import (
	"container/heap"

A priority job queue with Go's container/heap

priority-queue heap interfaces

Intermediate 9 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")