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.

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