What is the brute force approach and complexity for Union-Find (template)?

One label per node; a union renames every node of one group with time complexity O(N · Q) and space complexity O(N).

What is the optimal approach and complexity for Union-Find (template)?

Parent pointers; find each root, link roots (smaller under bigger) with optimal time complexity O(Q · α(N)) and space complexity O(N).

How do you identify the pattern for Union-Find (template)?

Look for key signals in the prompt: "groups that merge over time" indicates Items join groups as the queries arrive → keep groups with one root each.; "type 1: join x and y" indicates A union: merge two groups, and never split them.; "type 2: are x and y connected?" indicates Compare the roots of the two items; no search over the graph is needed..

Union-Find (template)

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelUnion-Find (DSU), the base template

Complexity:O(N · Q)→O(Q · α(N))

Key Insight

Each group is a tree of parent pointers, and the root of the tree names the group. connected(x, y) compares find(x) with find(y). union(x, y) links one root under the other, so a union changes exactly one pointer and no node is renamed.

Core Validity Invariant

Two nodes are in one group exactly when they have the same root, so find(x) == find(y) is the whole connected check.

Problem

You have n nodes numbered 0 to n − 1. At the start, every node is alone in its own group.

You get a list of queries. Each query is [type, x, y]:

type 1 is a union: join the group of x with the group of y.
type 2 asks are x and y connected?: say whether x and y are in the same group right now. Record true or false.

Return the answers to the type-2 queries, in the order they appear.

Input

n, the number of nodes, and queries, a list of [type, x, y] triples.

Output

A list of booleans (vector<bool>): one answer for each type-2 query, in the same order.

Example 1

Input: n = 5, queries = [[1,0,1], [2,0,1], [2,1,2], [1,1,2], [2,0,2]]

Output: [true, false, true]

After joining 0 and 1, the nodes 0 and 1 are connected, but 2 is still alone. After joining 1 and 2, the group is {0, 1, 2}, so 0 and 2 are connected.

Example 2

Input: n = 4, queries = [[1,0,1], [1,2,3], [2,0,3], [1,1,3], [2,0,2]]

Output: [false, true]

The groups are {0, 1} and {2, 3} when we ask about 0 and 3, so the answer is no. Joining 1 and 3 merges all four nodes, so 0 and 2 are connected.

Constraints

• Every node number x and y is in the range 0 to n − 1.
• The type is 1 (union) or 2 (connected?).
• A node is always connected to itself.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A union changes which nodes share a group. What stays the same for every other group?
2.
How could I answer "are x and y connected?" without looking at every node in the group?
3.
If every group had one name, what would a union have to rename?
4.
If each node stores only one parent, how do I find the group's name from any node in it?
5.
When I join two groups, do I attach the two nodes from the query, or something else?

Brute force approach

Idea

Keep label[v], the name of v's group. A connected query is label[x] == label[y], which is one comparison. A union (x, y) renames every node that has the name label[y] to label[x], so each union walks the whole group.

Thinking process

1
Start with label[v] = v. Every node is its own group.
2
Two nodes are in one group exactly when their labels are equal, so a connected query is a single comparison.
3
For a union, every node that carries the other side's label must change. On the dry run, union(5, 0) renames the four nodes of group 0 (nodes 0, 1, 2 and 3) to the name 4, because node 5 already had 4.
4
A long run of unions can rename almost every node many times over, so the work grows with n for each union.

Visual

Each cell is a node and its number is the group name. Orange = renamed by this union. Blue = the two nodes in a connected query.

Quick-find: rename the whole group

n = 6, queries: union(0, 1), union(2, 3), connected(0, 3)?, union(1, 3), connected(3, 0)?, union(4, 5), union(5, 0), connected(5, 2)?, union(0, 2), connected(4, 1)?

step 1/12

label

State

cells renamed so far: 0
answers: none yet

Every node has its own name

Quick-find keeps one name per node. Two nodes are in one group when their names are equal, so a connected check is one comparison.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<bool> solve(int n, vector<array<int, 3>>& queries) {
        // label[v] = the name of v's group. At the start every node has its own name.
        vector<int> label(n);
        iota(label.begin(), label.end(), 0);

        vector<bool> answers;
        for (auto& q : queries) {
            int type = q[0], x = q[1], y = q[2];
            if (type == 1) {
                int from = label[y], to = label[x];
                if (from == to) continue;              // already one group
                // Rename every member of y's group to x's name. O(n) work for one union.
                for (int v = 0; v < n; v++)
                    if (label[v] == from) label[v] = to;
            } else {
                // Same name = same group. This part is O(1).
                answers.push_back(label[x] == label[y]);
            }
        }
        return answers;
    }
};

import java.util.*;

class Solution {
    public List<Boolean> solve(int n, int[][] queries) {
        // label[v] = the name of v's group. At the start every node has its own name.
        int[] label = new int[n];
        for (int i = 0; i < n; i++) {
            label[i] = i;
        }

        List<Boolean> answers = new ArrayList<>();
        for (int[] q : queries) {
            int type = q[0], x = q[1], y = q[2];
            if (type == 1) {
                int from = label[y], to = label[x];
                if (from == to) continue;              // already one group
                // Rename every member of y's group to x's name. O(n) work for one union.
                for (int v = 0; v < n; v++) {
                    if (label[v] == from) label[v] = to;
                }
            } else {
                // Same name = same group. This part is O(1).
                answers.add(label[x] == label[y]);
            }
        }
        return answers;
    }
}

from typing import List

class Solution:
    def solve(self, n: int, queries: List[List[int]]) -> List[bool]:
        # label[v] = the name of v's group. At the start every node has its own name.
        label = list(range(n))

        answers: List[bool] = []
        for q in queries:
            qtype, x, y = q[0], q[1], q[2]
            if qtype == 1:
                from_grp, to_grp = label[y], label[x]
                if from_grp == to_grp:
                    continue                           # already one group
                # Rename every member of y's group to x's name. O(n) work for one union.
                for v in range(n):
                    if label[v] == from_grp:
                        label[v] = to_grp
            else:
                # Same name = same group. This part is O(1).
                answers.append(label[x] == label[y])
        return answers

export function solve(n: number, queries: number[][]): boolean[] {
    // label[v] = the name of v's group. At the start every node has its own name.
    const label: number[] = Array.from({ length: n }, (_, i) => i);

    const answers: boolean[] = [];
    for (const q of queries) {
        const type = q[0], x = q[1], y = q[2];
        if (type === 1) {
            const from = label[y], to = label[x];
            if (from === to) continue;              // already one group
            // Rename every member of y's group to x's name. O(n) work for one union.
            for (let v = 0; v < n; v++) {
                if (label[v] === from) label[v] = to;
            }
        } else {
            // Same name = same group. This part is O(1).
            answers.push(label[x] === label[y]);
        }
    }
    return answers;
}

Complexity

Time O(N · Q)Space O(N)

N is the number of nodes and Q the number of queries. The label array has one entry per node. Each union can rewrite up to N entries; a connected query only reads two labels.

Optimized approach

Idea

Start from brute force

Quick-find stores the group's name on every member, so a union has to rename each member of one group.

Find the repeated work

The same nodes are renamed again and again as groups grow. A union only needs to change how two names are linked, not every member.

Define the state — what variables do I need?

parent[v]: The node one step up from v. A root has parent[v] = v.
sz[r]: Size of the tree whose root is r. Only roots keep a meaningful size.
groups: How many trees (groups) exist now. It starts at n and drops by 1 on every union that really joins two trees.

Define validity

Two nodes are in one group exactly when they have the same root, so find(x) == find(y) is the whole connected check.

Define the transitions — when does each pointer move, and why is it safe?

union(x, y)

a = find(x), b = find(y). If a == b, do nothing. Otherwise parent[smaller root] = bigger root.

Linking roots merges the two trees and touches no other node. Linking the query's nodes instead could cut a node away from its own tree.

connected(x, y)

return find(x) == find(y)

Two nodes share a root only when they are in the same tree, because each tree has exactly one root.

Inside find, while walking up

parent[x] = parent[parent[x]]; then x = parent[x]

Path halving skips one level on each step. The root does not change, so later finds get shorter.

What does the current window add to the answer?

A type-2 query contributes one comparison of two roots to the answer list. A type-1 query only changes the trees, and groups drops by one whenever the union really merges two trees.

Code & Implementation

optimal.cpp

// Union-Find with path compression + union by size.
struct DSU {
    vector<int> parent, sz;
    int groups;
    DSU(int n) : parent(n), sz(n, 1), groups(n) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);             // hang the smaller tree under the bigger one
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
};

class Solution {
public:
    vector<bool> solve(int n, vector<array<int, 3>>& queries) {
        DSU dsu(n);
        vector<bool> answers;
        for (auto& q : queries) {
            int type = q[0], x = q[1], y = q[2];
            if (type == 1) {
                dsu.unite(x, y);                   // merges the two groups (no-op if already one)
            } else {
                // Compare the ROOTS. Two nodes can have different parents and still share a root.
                answers.push_back(dsu.find(x) == dsu.find(y));
            }
        }
        return answers;
    }
};

import java.util.*;

// Union-Find with path compression + union by size.
class DSU {
    int[] parent, sz;
    int groups;

    public DSU(int n) {
        parent = new int[n];
        sz = new int[n];
        groups = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    public int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    public boolean unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) {
            int tmp = a; a = b; b = tmp;             // hang the smaller tree under the bigger one
        }
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
}

class Solution {
    public List<Boolean> solve(int n, int[][] queries) {
        DSU dsu = new DSU(n);
        List<Boolean> answers = new ArrayList<>();
        for (int[] q : queries) {
            int type = q[0], x = q[1], y = q[2];
            if (type == 1) {
                dsu.unite(x, y);                   // merges the two groups (no-op if already one)
            } else {
                // Compare the ROOTS. Two nodes can have different parents and still share a root.
                answers.add(dsu.find(x) == dsu.find(y));
            }
        }
        return answers;
    }
}

from typing import List

# Union-Find with path compression + union by size.
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.groups = n

    def find(self, x: int) -> int:                              # the root that names x's group
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]         # path compression (halving): skip a level each step
            x = self.parent[x]
        return x

    def unite(self, a: int, b: int) -> bool:                     # False when a and b were already in one group
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a                                         # hang the smaller tree under the bigger one
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.groups -= 1
        return True

class Solution:
    def solve(self, n: int, queries: List[List[int]]) -> List[bool]:
        dsu = DSU(n)
        answers: List[bool] = []
        for q in queries:
            qtype, x, y = q[0], q[1], q[2]
            if qtype == 1:
                dsu.unite(x, y)                   # merges the two groups (no-op if already one)
            else:
                # Compare the ROOTS. Two nodes can have different parents and still share a root.
                answers.append(dsu.find(x) == dsu.find(y))
        return answers

// Union-Find with path compression + union by size.
class DSU {
    parent: number[];
    sz: number[];
    groups: number;

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.sz = new Array(n).fill(1);
        this.groups = n;
    }

    find(x: number): number {                              // the root that names x's group
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];  // path compression (halving): skip a level each step
            x = this.parent[x];
        }
        return x;
    }

    unite(a: number, b: number): boolean {                 // false when a and b were already in one group
        a = this.find(a);
        b = this.find(b);
        if (a === b) return false;
        if (this.sz[a] < this.sz[b]) {
            const tmp = a; a = b; b = tmp;                 // hang the smaller tree under the bigger one
        }
        this.parent[b] = a;
        this.sz[a] += this.sz[b];
        this.groups--;
        return true;
    }
}

export function solve(n: number, queries: number[][]): boolean[] {
    const dsu = new DSU(n);
    const answers: boolean[] = [];
    for (const q of queries) {
        const type = q[0], x = q[1], y = q[2];
        if (type === 1) {
            dsu.unite(x, y);                   // merges the two groups (no-op if already one)
        } else {
            // Compare the ROOTS. Two nodes can have different parents and still share a root.
            answers.push(dsu.find(x) === dsu.find(y));
        }
    }
    return answers;
}

Complexity

Time O(Q · α(N))Space O(N)

α is the inverse Ackermann function, which is below 5 for any input that fits in memory. Union by size keeps every tree at depth at most log N, and path halving makes repeated finds shorter still. Space is one parent and one size per node.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	One label per node; a union renames every node of one group	O(N · Q)	O(N)
Optimal	Parent pointers; find each root, link roots (smaller under bigger)	O(Q · α(N))	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“groups that merge over time”Items join groups as the queries arrive → keep groups with one root each.
“type 1: join x and y”A union: merge two groups, and never split them.
“type 2: are x and y connected?”Compare the roots of the two items; no search over the graph is needed.

Items that merge over time+union(x, y) joins two groups+connected(x, y) means same root→Union-Find (DSU), the base template

This is the base template of the whole pattern. Every later question keeps the same two operations, find and unite, and only changes what an item stands for or when two items are united. Here the nodes are plain numbers and the answers come straight from the roots, with nothing else to count.

Don't make this mistake

Linking the two nodes instead of their roots

✗ void unite(int a, int b) { parent[b] = a; }

✓ bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; parent[b] = a; return true; }

Pattern-confusion trap: this looks like a union, but it only works on nodes that are already roots. On the dry run, after union(0, 1) and union(2, 3), node 3 hangs under 2. Then union(1, 3) with the wrong code sets parent[3] = 1. Node 3 leaves its group, so the group {2, 3} is split and connected(2, 3) returns false. With find first, the roots are 0 and 2, so parent[2] = 0 and all four nodes stay together.

Comparing one step up instead of the roots

✗ return parent[x] == parent[y];

✓ return find(x) == find(y);

parent[x] only points one level up. After union(1, 3) on the dry run, parent[3] = 2 and parent[2] = 0. They differ, yet 2 and 3 are in one group. Always compare the roots.

Hanging the first root under the second, with no size rule

✗ parent[rb] = ra; // always the same direction

✓ if (sz[ra] < sz[rb]) swap(ra, rb); parent[rb] = ra; sz[ra] += sz[rb];

Always hanging the same side under the other can build a chain 0 ← 1 ← 2 ← … ← n−1. Then find walks n steps every time. The size rule keeps trees shallow, so every find stays short.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture