Path Compression in Union Find in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the root parent of a node in Union Find.

DSA Typescript

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

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

Aparent[x]

Bparent

Cx

Dx + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using x instead of parent[x] causes infinite recursion.

Using parent instead of parent[x] causes type errors.

The find function recursively finds the root parent of x by following parent pointers. The correct recursive call is find(parent, parent[x]) to move up the tree.

2fill in blank

medium

Complete the code to perform path compression in the find function.

DSA Typescript

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

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

Ax

Bfind(parent, x)

Cparent[x]

Dfind(parent, parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x does not compress the path.

Assigning parent[x] to find(parent, x) causes infinite recursion.

Path compression sets parent[x] to the root parent found by recursively calling find on parent[x]. This flattens the tree for faster future queries.

3fill in blank

hard

Fix the error in the union function to correctly merge two sets.

DSA Typescript

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

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

ArootY

By

CrootX

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using x or y instead of rootX causes incorrect merges.

Using rootY as index causes runtime errors.

To merge two sets, we set the parent of rootX to rootY. Using rootX ensures the root of x's set points to rootY.

4fill in blank

hard

Fill both blanks to implement union by rank optimization.

DSA Typescript

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

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

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using == or != in the first two conditions causes wrong merges.

Swapping > and < breaks the rank logic.

Union by rank attaches the smaller tree under the larger tree. If rank[rootX] > rank[rootY], rootY points to rootX. If rank[rootX] < rank[rootY], rootX points to rootY.

5fill in blank

hard

Fill all three blanks to implement the find function with path compression and union by rank.

DSA Typescript

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

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

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

Afind(parent, rank, parent[x])

B>

C<

Dfind(parent, parent[x])

Attempts:

3 left

💡 Hint

Common Mistakes

Using find(parent, parent[x]) misses the rank parameter.

Swapping > and < breaks union by rank logic.

The find function uses path compression by recursively calling find with parent[x] and assigning the result to parent[x]. The union function compares ranks with > and < to decide which root becomes parent.