Path Compression in Union Find in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of find operation with path compression

What is the output of the following TypeScript code that uses path compression in a Union Find structure?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    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[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.find(2));
console.log(uf.parent);

A

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

B

0
[0, 0, 0, 3, 3]

C

1
[0, 0, 1, 3, 3]

D

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

💡 Hint

Remember that path compression updates the parent of each node visited during find to the root.

The find operation with path compression sets the parent of nodes 1 and 2 directly to 0, the root of their set. So uf.find(2) returns 0, and the parent array updates to [0, 0, 0, 3, 3].

🧠 Conceptual

intermediate

Effect of path compression on parent array

After performing union(0,1), union(1,2), and then calling find(2) with path compression, what will be the state of the parent array for a Union Find of size 4 initialized as [0,1,2,3]?

A [0, 0, 0, 3]

B [0, 1, 0, 3]

C [0, 1, 2, 3]

D [1, 1, 1, 3]

💡 Hint

Path compression sets all nodes on the find path directly to the root.

Calling find(2) compresses the path so that nodes 1 and 2 point directly to 0, the root. So parent array becomes [0, 0, 0, 3].

🔧 Debug

advanced

Identify the error in path compression implementation

What error will the following TypeScript code produce when calling uf.find(2)?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.find(this.parent[x]);
    }
    return this.parent[x];
  }
}

const uf = new UnionFind(3);
uf.parent = [0, 2, 1];
console.log(uf.find(2));

A Returns 0 without error

B TypeError: Cannot read property of undefined

C Stack overflow due to infinite recursion

D Returns 2 without error

💡 Hint

Check if the recursive call updates the parent array.

The find method calls itself recursively but does not update parent[x] with the result, causing infinite recursion when parent[x] != x.

❓ Predict Output

advanced

Parent array after multiple unions and finds with path compression

What is the parent array after executing the following code?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    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[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(6);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
uf.union(4, 5);
uf.union(2, 5);
uf.find(5);
uf.find(4);
console.log(uf.parent);

A [0, 0, 0, 0, 0, 0]

B [0, 0, 0, 0, 3, 3]

C [0, 1, 2, 3, 4, 5]

D [0, 0, 0, 3, 3, 0]

💡 Hint

The union operations connect all nodes into one set with root 0. Path compression updates parents.

All nodes 0-5 become connected with root 0. The find(5) compresses paths so all parents point to 0.

🧠 Conceptual

expert

Time complexity impact of path compression in Union Find

Which statement best describes the effect of path compression on the time complexity of Union Find operations?

A Path compression changes the space complexity of Union Find from linear to logarithmic.

B Path compression increases the worst-case time complexity of union operations to linear time.

C Path compression has no effect on the time complexity of find or union operations.

D Path compression reduces the amortized time complexity of find operations to nearly constant, specifically inverse Ackermann function time.

💡 Hint

Consider how path compression flattens the tree structure over time.

Path compression flattens the tree, making future find operations very fast. The amortized time per operation becomes almost constant, bounded by the inverse Ackermann function.