Path Compression in Union Find in DSA Typescript

Mental Model

Path compression makes finding the group leader faster by flattening the tree structure during searches.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone on the path to point directly to the oldest ancestor, so next time you find the ancestor faster.

Before path compression:
1 -> 2 -> 3 -> 4 -> null
After path compression:
1 -> 4
2 -> 4
3 -> 4
4 -> null

Dry Run Walkthrough

Input: Union-Find with elements 1 to 4, unions: union(1,2), union(2,3), union(3,4), then find(1)

Goal: Show how path compression flattens the tree when finding the leader of element 1

Step 1: union(1,2) links 1's leader to 2

1 -> 2 -> null
2 -> null
3 -> null
4 -> null

Why: We connect 1 and 2 so they share the same leader

Step 2: union(2,3) links 2's leader to 3

1 -> 2 -> 3 -> null
2 -> 3 -> null
3 -> null
4 -> null

Why: We connect 2 and 3, extending the chain

Step 3: union(3,4) links 3's leader to 4

1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
3 -> 4 -> null
4 -> null

Why: We connect 3 and 4, making 4 the leader

Step 4: find(1) traverses from 1 to 4, compressing path

1 -> 4
2 -> 4
3 -> 4
4 -> null

Why: Path compression updates all nodes on path to point directly to leader 4

Result:

1 -> 4
2 -> 4
3 -> 4
4 -> null
Leader of 1 is 4

Annotated Code

DSA Typescript

class UnionFind {
  parent: number[];

  constructor(size: number) {
    this.parent = Array(size + 1).fill(0).map((_, i) => i);
  }

  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 rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) {
      this.parent[rootA] = rootB; // link rootA to rootB
    }
  }
}

// Driver code
const uf = new UnionFind(4);
uf.union(1, 2);
uf.union(2, 3);
uf.union(3, 4);

console.log('Parent array after unions:', uf.parent.slice(1).join(' '));

const leader = uf.find(1);
console.log('Leader of 1 is', leader);
console.log('Parent array after path compression:', uf.parent.slice(1).join(' '));

if (this.parent[x] !== x) {

check if current node is not leader

this.parent[x] = this.find(this.parent[x]); // path compression

recursively find leader and update current node to point directly to leader

return this.parent[x];

return leader of current node

const rootA = this.find(a);

find leader of element a

const rootB = this.find(b);

find leader of element b

if (rootA !== rootB) {

only union if leaders differ

this.parent[rootA] = rootB; // link rootA to rootB

attach rootA's tree under rootB to merge sets

Output

Parent array after unions: 2 3 4 4

Leader of 1 is 4

Parent array after path compression: 4 4 4 4

Complexity Analysis

Time: O(α(n)) per find/union operation because path compression flattens trees making future finds almost constant time

Space: O(n) for storing parent array for n elements

vs Alternative: Without path compression, find can be O(n) in worst case due to tall trees; path compression reduces this to nearly O(1)

Edge Cases

Finding leader of an element that is its own leader

Returns the element itself immediately without recursion

DSA Typescript

if (this.parent[x] !== x) {

Union of two elements already in the same set

No change to parent array as leaders are equal

DSA Typescript

if (rootA !== rootB) {

Union and find on single element set

Find returns element itself; union links sets correctly

DSA Typescript

if (this.parent[x] !== x) {

When to Use This Pattern

When you see problems about grouping elements and quickly checking if two elements belong to the same group, use Union Find with path compression to speed up repeated queries.

Common Mistakes

Mistake: Not updating the parent during find, missing path compression
Fix: Assign parent[x] = find(parent[x]) to flatten the tree

Mistake: Linking parents incorrectly in union causing cycles
Fix: Always link root of one set to root of another after finding leaders

Summary

Path compression speeds up finding the leader by making nodes point directly to the leader.

Use it when you need fast repeated union and find operations on disjoint sets.

The key insight is flattening the tree during find to make future finds faster.

Practice

1. What is the main purpose of path compression in a Union Find data structure?

easy

A. To sort elements inside each set

B. To speed up the find operation by flattening the tree

C. To delete elements from the set efficiently

D. To merge two sets without checking their roots

Solution

1. Step 1: Understand the find operation

   The find operation locates the root of an element's set in Union Find.

2. Step 2: Role of path compression

   Path compression flattens the tree by making nodes point directly to the root, speeding up future find calls.

3. Final Answer:

   To speed up the find operation by flattening the tree -> Option B

4. Quick Check:

   Path compression = faster find [OK]

Hint: Path compression flattens trees to speed up find [OK]

Common Mistakes:

• Confusing path compression with union operation
• Thinking it deletes elements
• Assuming it sorts elements

2. Which of the following is the correct TypeScript syntax for the find function with path compression in Union Find?

easy

A. function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; }

B. function find(x: number): number { while (parent[x] !== x) x = parent[x]; return x; }

C. function find(x: number): number { if (parent[x] === x) return x; else return find(parent[x]); }

D. function find(x: number): number { parent[x] = x; return x; }

Solution

1. Step 1: Identify path compression in code

   Path compression updates parent[x] to root during recursion.

2. Step 2: Check each option

   function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] recursively, implementing path compression correctly.

3. Final Answer:

   function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } -> Option A

4. Quick Check:

   Path compression updates parent[x] recursively [OK]

Hint: Look for recursive parent update in find [OK]

Common Mistakes:

• Missing parent update for path compression
• Using loop without updating parent
• Returning without compression

3. Given the following TypeScript code snippet, what will be the output of console.log(parent) after calling find(3)?

let parent = [0, 0, 1, 2, 4];
function find(x: number): number {
  if (parent[x] !== x) parent[x] = find(parent[x]);
  return parent[x];
}
find(3);
console.log(parent);

medium

A. [0, 0, 1, 2, 4]

B. [0, 1, 1, 1, 4]

C. [0, 0, 2, 2, 4]

D. [0, 0, 0, 0, 4]

Solution

1. Step 1: Trace find(3) calls

   find(3) checks parent[3] = 2, calls find(2). find(2) checks parent[2] = 1, calls find(1). find(1) checks parent[1] = 0, calls find(0). find(0) returns 0 since parent[0] = 0.

2. Step 2: Apply path compression updates

   Unwinding: parent[1] = 0 (already), returns 0; parent[2] = 0, returns 0; parent[3] = 0, returns 0. Final parent = [0, 0, 0, 0, 4].

3. Final Answer:

   [0, 0, 0, 0, 4] -> Option D

4. Quick Check:

   Path compression sets all path nodes to root [OK]

Hint: Follow recursive calls and update parents on return [OK]

Common Mistakes:

• Not updating parent array after recursion
• Confusing indices and values
• Assuming all parents become root immediately

4. Identify the bug in this TypeScript find function implementing path compression:

function find(x: number): number {
  if (parent[x] === x) return x;
  find(parent[x]);
  return parent[x];
}

medium

A. Missing assignment to parent[x] for path compression

B. Incorrect base case condition

C. Function should return void

D. Using recursion without a return statement

Solution

1. Step 1: Analyze recursion and return

   The function calls find(parent[x]) but does not assign its result back to parent[x].

2. Step 2: Identify missing path compression update

   Without parent[x] = find(parent[x]), path compression does not happen, so the tree is not flattened.

3. Final Answer:

   Missing assignment to parent[x] for path compression -> Option A

4. Quick Check:

   Path compression requires updating parent[x] [OK]

Hint: Ensure recursive find result is assigned to parent[x] [OK]

Common Mistakes:

• Forgetting to assign recursive call result
• Returning without recursion
• Wrong base case logic

5. You have a Union Find with parent = [0, 0, 1, 2, 3, 5]. After performing union(4, 5) and then find(5) with path compression, what will be the final parent array?

hard

A. [0, 0, 1, 2, 3, 4]

B. [0, 0, 1, 2, 4, 4]

C. [0, 0, 0, 0, 0, 0]

D. [0, 0, 1, 2, 3, 0]

Solution

1. Step 1: Perform union(4, 5)

   Initial parent = [0, 0, 1, 2, 3, 5]. Simple union links by setting parent[5] = 4. Now parent = [0, 0, 1, 2, 3, 4].

2. Step 2: Call find(5) with path compression

   find(5): parent[5]=4 -> find(4): parent[4]=3 -> find(3)=2 -> find(2)=1 -> find(1)=0 -> find(0)=0.

3. Step 3: Update parent array after compression

   Unwinding sets parent[4]=0, parent[3]=0, parent[2]=0, parent[1]=0, but parent[5] remains 4 because find(5) returns 0 but parent[5] was set to 4 and not updated in this code snippet. So after path compression, parent array is [0, 0, 1, 2, 0, 4] if path compression is applied only on the path from 5 to root. However, since find(5) calls find(4), which calls find(3), etc., and path compression updates parent[x] = find(parent[x]) recursively, parent[5] should be updated to 0 as well. So final parent array is [0, 0, 0, 0, 0, 0].

4. Final Answer:

   [0, 0, 0, 0, 0, 0] -> Option C

5. Quick Check:

   Union sets and compress path update parents [OK]

Hint: Union sets then compress path to update parents [OK]

Common Mistakes:

• Not updating parent after union
• Ignoring path compression updates
• Assuming parent stays same after find