Union Find: Practice Problems with Solutions
Welcome to the practice problems for Union Find. If you need a refresher on the intuition, start with the concept guide , and the code templates have the pattern in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.
Recommended Study Order
The problems are ordered by difficulty, but the progression matters as much as the individual solutions.
- Find if Path Exists in Graph teaches the core query: does element A share a group with element B? Everything else builds on this.
- Number of Provinces adds component counting, where the answer is the number of distinct roots.
- Redundant Connection adds cycle detection with 1-based node numbering, which is a separate modeling skill.
- Number of Islands shows how to flatten a grid into a graph by converting each cell to an index.
- Accounts Merge shows how to map non-integer elements, like email strings, onto indices.
- Min Cost to Connect All Points combines sorting with Union Find in Kruskal’s algorithm.
- Making A Large Island is the hardest: grid modeling plus component sizes, with one flipped cell connecting neighboring islands.
Easy Problems
1. Find if Path Exists in Graph
LeetCode 1971 | Difficulty: Easy
Brief: Given n nodes and a list of undirected edges, return true if there is a path between two given nodes.
Why this pattern: This is the purest form of the connectivity query. Union all edges, then check whether the two nodes share a root.
Key Insight: After every edge is processed, find(source) === find(destination) is the entire answer. No traversal, no visited set.
Visual:
graph LR
E1["union(0,1)"] --> E2["union(1,2)"]
E2 --> E3["union(2,4)"]
E3 --> C{"find(0) == find(4)?"}
C -->|"Yes"| T["Path exists"]
C -->|"No"| F["No path"]
Code:
var validPath = function(n, edges, source, destination) {
if (source === destination) return true;
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const [u, v] of edges) {
const rootU = find(u);
const rootV = find(v);
if (rootU !== rootV) parent[rootU] = rootV;
}
return find(source) === find(destination);
};The whole problem is one pass of unions followed by one connectivity check. The early return for source == destination is optional, but it avoids the pass entirely when the answer is trivially true. The run time is
2. Number of Provinces
LeetCode 547 | Difficulty: Medium
Brief: Given an adjacency matrix of direct connections between cities, return the number of provinces, where a province is a group of directly or indirectly connected cities.
Why this pattern: This is component counting. Every connected pair gets unioned, and the answer is the number of distinct groups left.
Key Insight: Start the count at N and decrement it once per successful union. The count never needs to be recomputed, because every merge reduces the number of groups by exactly one.
Visual:
graph TD
M["isConnected = [1 1 0 / 1 1 0 / 0 0 1]"] --> U["union(0,1)"]
U --> C["City 0 and City 1 in one province"]
C --> R["City 2 alone"]
R --> A["Answer: 2 provinces"]
Code:
var findCircleNum = function(isConnected) {
const n = isConnected.length;
const parent = Array.from({ length: n }, (_, i) => i);
let count = n;
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isConnected[i][j] === 1) {
const rootI = find(i);
const rootJ = find(j);
if (rootI !== rootJ) {
parent[rootI] = rootJ;
count--;
}
}
}
}
return count;
};The inner loop starts at i + 1 because the matrix is symmetric and the diagonal is always 1. Every pair is examined exactly once from one side. The matrix forces
Medium Problems
3. Redundant Connection
LeetCode 684 | Difficulty: Medium
Brief: A graph that started as a tree of n nodes has one extra edge. Return the extra edge that, if removed, turns it back into a tree.
Why this pattern: This is cycle detection with Union Find. Adding an edge whose endpoints are already connected closes a cycle.
Key Insight: The first edge that fails to union is the answer. Because the graph started as a tree, exactly one edge closes a cycle, and edges are processed in order.
Visual:
graph LR
N1((1)) --- N2((2))
N1 --- N3((3))
N2 -- "redundant [2,3]" --- N3
Code:
var findRedundantConnection = function(edges) {
// Nodes are numbered 1..n, so the array needs n+1 slots
const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const [u, v] of edges) {
const rootU = find(u);
const rootV = find(v);
if (rootU === rootV) return [u, v]; // already connected: this edge closes a cycle
parent[rootU] = rootV;
}
};The one detail to get right is the array size. Nodes are labeled 1 through n, so edges.length + 1 slots are needed. Returning the edge immediately is correct here, because the first failed union is the edge that closes the cycle, and the problem wants the edge that appears last in the input, which is the one being processed. The run time is
4. Number of Islands
LeetCode 200 | Difficulty: Medium
Brief: Count the number of islands in a 2D grid, where an island is a group of adjacent land cells surrounded by water.
Why this pattern: Each land cell becomes a node, and adjacent land cells are unioned. The number of islands is the number of components, which the count-down trick tracks directly.
Key Insight: Flatten each cell (r, c) to the index r * cols + c. Checking only the right and down neighbors is enough, because every adjacent pair is seen from exactly one side.
Visual:
graph TD
G["grid = 1 1 0 / 0 1 0 / 0 0 1"] --> U["Union adjacent land cells"]
U --> S1["Island A: 3 cells"]
U --> S2["Island B: 1 cell"]
S1 --> R["Answer: 2 islands"]
S2 --> R
Code:
var numIslands = function(grid) {
if (grid.length === 0) return 0;
const rows = grid.length, cols = grid[0].length;
const parent = Array.from({ length: rows * cols }, (_, i) => i);
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') count++;
}
}
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) {
parent[rootA] = rootB;
count--;
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '0') continue;
const idx = r * cols + c;
if (r + 1 < rows && grid[r + 1][c] === '1') union(idx, (r + 1) * cols + c);
if (c + 1 < cols && grid[r][c + 1] === '1') union(idx, r * cols + c + 1);
}
}
return count;
};The count starts at the number of land cells and drops once per successful union, so it ends as the number of islands without a separate scan. Checking only right and down neighbors covers every adjacency because the other two directions are seen from the other side of the pair. The run time is
5. Accounts Merge
LeetCode 721 | Difficulty: Medium
Brief: Merge accounts that share at least one email address, keeping each person’s emails sorted under their name.
Why this pattern: Emails are the nodes, and two emails belong to the same person when they appear in the same account. The email strings need a mapping to indices first.
Key Insight: Union the first email of each account with every other email in that account. Afterwards, emails that share a root belong to one person, and each group is sorted before it is returned.
Visual:
graph LR
A["johnsmith@mail.com"] --- B["john_newyork@mail.com"]
A --- C["john00@mail.com"]
D["mary@mail.com"] --- E["Separate component"]
Code:
var accountsMerge = function(accounts) {
const emailToIndex = new Map();
const emailToName = new Map();
let index = 0;
for (const account of accounts) {
const name = account[0];
for (let i = 1; i < account.length; i++) {
if (!emailToIndex.has(account[i])) {
emailToIndex.set(account[i], index);
emailToName.set(account[i], name);
index++;
}
}
}
const parent = Array.from({ length: index }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const account of accounts) {
const first = emailToIndex.get(account[1]);
for (let i = 2; i < account.length; i++) {
const rootFirst = find(first);
const rootOther = find(emailToIndex.get(account[i]));
if (rootFirst !== rootOther) parent[rootOther] = rootFirst;
}
}
const groups = new Map();
for (const [email, idx] of emailToIndex) {
const root = find(idx);
if (!groups.has(root)) groups.set(root, []);
groups.get(root).push(email);
}
const result = [];
for (const emails of groups.values()) {
emails.sort();
result.push([emailToName.get(emails[0]), ...emails]);
}
return result;
};The skill in this problem is the mapping. Emails become indices through a dictionary, and each account unions its first email with every other email it contains. Emails that share an account end up in one component, and the final pass groups them by root, sorts each group, and attaches the name from the first email. The run time is
6. Min Cost to Connect All Points
LeetCode 1584 | Difficulty: Medium
Brief: Connect all points in a plane with minimum total cost, where the cost of connecting two points is their Manhattan distance.
Why this pattern: This is Kruskal’s algorithm for a minimum spanning tree. Union Find supplies the near-constant cycle check that makes the greedy edge selection safe.
Key Insight: Generate every pairwise edge, sort by Manhattan distance, and accept an edge only when its endpoints are not already connected. Stop as soon as n-1 edges are accepted.
Visual:
graph LR
P2[("(2,2)")] -- "cost 3" --- P3[("(5,2)")]
P1[("(0,0)")] -- "cost 4" --- P2
P3 -- "cost 4" --- P4[("(7,0)")]
P2 -- "cost 9" --- P5[("(3,10)")]
Code:
var minCostConnectPoints = function(points) {
const n = points.length;
const edges = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges.push([dist, i, j]);
}
}
edges.sort((a, b) => a[0] - b[0]);
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
let total = 0;
let used = 0;
for (const [dist, u, v] of edges) {
const rootU = find(u);
const rootV = find(v);
if (rootU !== rootV) {
parent[rootU] = rootV;
total += dist;
if (++used === n - 1) break;
}
}
return total;
};The pair generation is O(N²) because every pair of points becomes a candidate edge. Sorting those edges dominates the cost at
Hard Problems
7. Making A Large Island
LeetCode 827 | Difficulty: Hard
Brief: In an n x n grid of 0s and 1s, change at most one 0 to a 1 and return the size of the largest island that can be formed.
Why this pattern: This is component counting with sizes. Union adjacent land cells, record each component’s size, then evaluate what happens when one water cell becomes land.
Key Insight: For each water cell, collect the distinct roots among its four neighbors and sum their sizes, plus one for the cell itself. The distinctness check matters: two neighbors can share a root, and counting it twice would inflate the answer.
Visual:
graph TD
G["grid = 1 1 0 / 0 1 0 / 0 0 1"] --> U["Union adjacent land cells"]
U --> S1["Island A: size 3"]
U --> S2["Island B: size 1"]
S1 --> Z["Flip one water cell between them"]
S2 --> Z
Z --> R["Merged island: size 5"]
Code:
var largestIsland = function(grid) {
const n = grid.length;
const parent = Array.from({ length: n * n }, (_, i) => i);
const size = new Array(n * n).fill(1);
let hasZero = false;
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) {
if (size[rootA] < size[rootB]) {
parent[rootA] = rootB;
size[rootB] += size[rootA];
} else {
parent[rootB] = rootA;
size[rootA] += size[rootB];
}
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 0) {
hasZero = true;
continue;
}
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 1) {
union(r * n + c, nr * n + nc);
}
}
}
}
if (!hasZero) return n * n;
let best = 0;
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 0) {
const seen = new Set();
let total = 1;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 1) {
const root = find(nr * n + nc);
if (!seen.has(root)) {
seen.add(root);
total += size[root];
}
}
}
best = Math.max(best, total);
}
}
}
return best;
};The first pass unions adjacent land cells and folds sizes together, which is the union by size variation from the template page . The second pass evaluates every water cell: it collects the distinct roots among the four neighbors and sums their sizes plus one. A water cell can border the same island on two sides, which is why the set is necessary. If the grid has no water cells, the whole grid is already one island. The run time is
These seven problems cover the full range of Union Find applications. Start with the connectivity query in Find if Path Exists in Graph, work through component counting, cycle detection, and the two modeling tricks (grids and string elements), and finish with Kruskal’s algorithm and the sized components in Making A Large Island. By the end, the pattern should feel like a reflex: read the problem, decide whether connectivity is the question, and reach for the template.