63. Union by Rank + Path Compression

PRO

Hard

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

Input: union(0, 1), union(2, 3), find(0), find(2)

Output: 0, 2

Explanation: After the union operations, 0 and 1 are in the same set with representative 0, and 2 and 3 are in the same set with representative 2. The find operations return these representatives.

Example 2:

Input: union(0, 1), union(1, 2), find(0), find(2), find(3)

Output: 0, 0, 3

Explanation: After the union operations, 0, 1 and 2 are in the same set with representative 0. Element 3 is in its own set with representative 3.

Example 3:

Input: n = 5, union(0, 1), union(2, 3), union(0, 2), find(0), find(1), find(2), find(3), find(4)

Output: 0, 0, 0, 0, 4

Explanation: Initially there are 5 disjoint sets {0}, {1}, {2}, {3}, {4}. union(0, 1) merges sets {0} and {1}. union(2, 3) merges {2} and {3}. union(0, 2) merges {0}, {1}, {2}, and {3}. find(0), find(1), find(2) and find(3) will all return the root of the set, which is 0. find(4) returns 4 since it wasn't part of any union operation.

Constraints:

Time Complexity

O(α(n))

Space Complexity

O(n)