Union Find Disjoint Set Data Structure in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array where each element is its own parent.

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = new Array(size);
    for (let i = 0; i < size; i++) {
      this.parent[i] = [1];
    }
  }
}

Drag options to blanks, or click blank then click option'

Ai

B0

C-1

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning all parents to 0 or -1 instead of their own index.

Using the size variable instead of the index.

Each element starts as its own parent, so we assign parent[i] = i.

2fill in blank

medium

Complete the code to find the root parent of an element with path compression.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Athis.parent[x]

Bx

Cthis.parent[this.parent[x]]

Dthis.find(this.parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x or parent[x] itself, which does not compress the path.

Using non-recursive or incorrect parent assignments.

Path compression sets the parent of x to the root parent found recursively by this.find(this.parent[x]).

3fill in blank

hard

Fix the error in the union method to correctly merge two sets by their root parents.

DSA Typescript

union(x: number, y: number): void {
  const rootX = this.find(x);
  const rootY = this.find(y);
  if (rootX !== rootY) {
    this.parent[[1]] = rootY;
  }
}

Drag options to blanks, or click blank then click option'

Ax

BrootX

Cy

DrootY

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent of x or y instead of their root parents.

Assigning parent of rootY to rootX which reverses the union.

We must set the parent of rootX to rootY to merge the sets.

4fill in blank

hard

Fill both blanks to implement a method that checks if two elements are in the same set.

DSA Typescript

connected(x: number, y: number): boolean {
  return this.find(x) [1] this.find(y)[2];
}

Drag options to blanks, or click blank then click option'

A===

B==

C!=

D!==

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality operators which return wrong results.

Using loose equality == instead of strict ===.

We check if the root parents are strictly equal using ===. The second blank is empty (no operator needed).

5fill in blank

hard

Fill all three blanks to implement union by rank optimization.

DSA Typescript

class UnionFind {
  parent: number[];
  rank: number[];
  constructor(size: number) {
    this.parent = new Array(size);
    this.rank = new Array(size).fill(0);
    for (let i = 0; i < size; i++) {
      this.parent[i] = i;
    }
  }

  union(x: number, y: number): void {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.rank[rootX] [1] this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] [2] this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX][3];
      }
    }
  }

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

Drag options to blanks, or click blank then click option'

A<

B>

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators reversing the logic.

Forgetting to increment rank when ranks are equal.

Union by rank attaches the smaller rank tree under the larger rank tree. If ranks are equal, attach one to the other and increment its rank.