Originally published on LeetCopilot Blog
DSU feels abstract until you sketch parent pointers. Here’s how to visualize path compression on grid problems.
Disjoint set union (DSU) feels abstract until you sketch parent pointers. This tutorial shows how to visualize path compression on grid island problems so you can explain every pointer hop in interviews.
TL;DR
- Union-find tracks connected components with parent pointers; path compression flattens chains to speed up future finds.
- Interviewers care because island problems hinge on efficient connectivity checks, and explaining pointer rewiring shows mastery.
- Core steps: map grid cells to ids, initialize each parent to itself, union …
Originally published on LeetCopilot Blog
DSU feels abstract until you sketch parent pointers. Here’s how to visualize path compression on grid problems.
Disjoint set union (DSU) feels abstract until you sketch parent pointers. This tutorial shows how to visualize path compression on grid island problems so you can explain every pointer hop in interviews.
TL;DR
- Union-find tracks connected components with parent pointers; path compression flattens chains to speed up future finds.
- Interviewers care because island problems hinge on efficient connectivity checks, and explaining pointer rewiring shows mastery.
- Core steps: map grid cells to ids, initialize each parent to itself, union neighbors, and compress paths during
find. - Beginners often forget to compress after recursion/iteration or mis-map 2D coordinates to 1D ids.
- You’ll see sketches, a TypeScript snippet, prep drills, and pitfalls, plus how tools like LeetCopilot support structured tracing.
Beginner-Friendly Explanations
What Path Compression Does
It rewires every node visited in find(x) to point directly to the root, turning tall trees into almost-flat stars.
Why It Matters for Grids
In island counting, you may call find thousands of times. Compression makes repeated neighbor checks cheap, keeping you within time limits noted in the sliding window learning path.
Step-by-Step Learning Guidance
1) Translate Grid to Node Ids
For an m x n grid, map cell (r, c) to id = r * n + c. Write these ids in the grid margin to avoid mistakes.
2) Initialize Parents and Ranks
Set parent[id] = id and optionally rank[id] = 0. Draw each node pointing to itself.
3) Union Adjacent Land Cells
For each land cell, union it with right and down neighbors if they are land. Draw arrows to show parent changes.
4) Apply Path Compression During Find
When calling find(x), rewrite every visited node to point to the root. Redraw the chain as a star to make the speedup visible.
5) Count Unique Roots
After unions, count distinct roots among land cells. This is your island count—announce it confidently in a mock interview routine.
Visualizable Example: DSU for Islands in TypeScript
class DSU {
parent: number[];
rank: number[];
constructor(size: number) {
this.parent = Array.from({ length: size }, (_, i) => i);
this.rank = Array(size).fill(0);
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(a: number, b: number): void {
const pa = this.find(a);
const pb = this.find(b);
if (pa === pb) return;
if (this.rank[pa] < this.rank[pb]) {
this.parent[pa] = pb;
} else if (this.rank[pb] < this.rank[pa]) {
this.parent[pb] = pa;
} else {
this.parent[pb] = pa;
this.rank[pa]++;
}
}
}
During a dry run, list the parent array after each union. Highlight cells whose parents changed during compression; the visual reinforces why the find calls become nearly O(1).
Practical Preparation Strategies
Color-Code Parent Changes
Use arrows and colors for each union step. Re-draw compressed paths to see the flattened tree shape.
Limit to Two Neighbor Checks
Union only right and down neighbors to avoid duplicate work. It keeps traces short and is standard in the AI prep primer sessions.
Narrate Coordinate Mappings
Say "cell (r, c) becomes id r*n + c" aloud. This reduces mistakes when copy-pasting formulas under pressure.
Compare With DFS/BFS
Explain why DSU avoids revisiting the grid compared to traversal. This contrast often impresses interviewers focused on optimization.
Common Mistakes to Avoid
Skipping Path Compression
Forgetting the assignment parent[x] = root leaves tall trees and TLE risks.
Reusing DSU Across Tests Without Reset
Always reinitialize parents and ranks per test case.
Mixing Up Row/Column in Id Mapping
Double-check that id = r * n + c; reversing it connects wrong cells.
Unioning Water Cells
Guard unions with a land check; connecting water distorts the island count.
FAQ
How do I verify my unions are correct?
Print parent arrays after each operation and ensure roots stay stable after extra find calls.
What should I know before DSU? Basic arrays and modular arithmetic. Light graph intuition helps but isn’t required.
Is path compression always needed?
For competitive runtimes, yes. Without it, deep chains make find slow.
How can I practice quickly? Dry run a 3x3 grid with two islands, then scale to 5x5. Light hints from LeetCopilot can verify your roots without spoiling solutions.
Conclusion
When you visualize union find path compression on grid islands, pointer updates feel simple. Mapping coordinates carefully, compressing every find, and narrating parent changes give you a clear interview story and reliable performance.
If you’re looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.