Bird
Raised Fist0
Data Structures Theoryknowledge~5 mins

Disjoint set (Union-Find) in Data Structures Theory - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime
Time Complexity: Disjoint set (Union-Find)
O(α(n))
Understanding Time Complexity

We want to understand how the time needed to perform union and find operations changes as the number of elements grows in a Disjoint Set (Union-Find) data structure.

How does the cost of these operations scale when we have more elements to manage?

Scenario Under Consideration

Analyze the time complexity of the following Union-Find operations with path compression and union by rank.


class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

This code manages groups of elements, quickly finding which group an element belongs to and joining groups together.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The find function uses recursion to climb up the parent links until it finds the root.
  • How many times: Each find call may traverse up to the height of the tree, but path compression flattens the tree over time.
  • Union calls use find twice and then link roots, which is a constant time operation after finds.
How Execution Grows With Input

Initially, trees may be tall, so find takes longer. But path compression quickly flattens trees, making future finds faster.

Input Size (n)Approx. Operations per find/union
10Very few steps, close to 1
100Few steps, slightly more than 1
1000Still very close to 1 due to flattening

Pattern observation: The cost grows very slowly and almost stays constant for large inputs because of path compression and union by rank.

Final Time Complexity

Time Complexity: O(α(n))

This means each operation takes almost constant time, where α(n) is the inverse Ackermann function, which grows so slowly it can be treated as a tiny constant for all practical input sizes.

Common Mistake

[X] Wrong: "Each find operation always takes time proportional to the number of elements because it might traverse the whole chain."

[OK] Correct: Path compression flattens the structure during finds, so after some operations, the trees become very shallow, making finds almost constant time.

Interview Connect

Understanding the efficient time complexity of Union-Find shows you can analyze how clever improvements affect performance, a valuable skill in many coding problems.

Self-Check

"What if we removed path compression from the find operation? How would the time complexity change?"

Practice

(1/5)
1. What is the main purpose of a Disjoint Set (Union-Find) data structure?
easy
A. To sort elements in ascending order
B. To store key-value pairs for fast lookup
C. To efficiently keep track of which elements belong to which groups
D. To perform arithmetic calculations on sets

Solution

  1. Step 1: Understand the role of Disjoint Set

    Disjoint Set is designed to manage groups of elements and quickly find which group an element belongs to.

  2. Step 2: Compare with other options

    Sorting, key-value storage, and arithmetic are unrelated to Disjoint Set's main function.

  3. Final Answer:

    To efficiently keep track of which elements belong to which groups -> Option C

  4. Quick Check:

    Disjoint Set = group tracking [OK]
Hint: Disjoint Set = fast group membership check [OK]
Common Mistakes:
  • Confusing Disjoint Set with sorting algorithms
  • Thinking it stores key-value pairs like a dictionary
  • Assuming it performs arithmetic on sets
2. Which of the following is the correct way to perform a union operation between two sets containing elements a and b in a Disjoint Set?
easy
A. merge(a, b)
B. union(a, b)
C. unionSet(a, b)
D. combine(a, b)

Solution

  1. Step 1: Identify standard Disjoint Set operation names

    The common and standard name for merging two sets is union.

  2. Step 2: Check other options

    Other names like unionSet, merge, or combine are not standard and may cause confusion.

  3. Final Answer:

    union(a, b) -> Option B

  4. Quick Check:

    Union operation = union(a, b) [OK]
Hint: Union operation is always called 'union' [OK]
Common Mistakes:
  • Using non-standard method names
  • Confusing union with find
  • Assuming merge or combine are standard
3. Consider the following sequence of operations on a Disjoint Set with elements {1, 2, 3, 4}:
union(1, 2)
union(3, 4)
union(2, 3)
find(4)

What is the result of find(4)?
medium
A. 4
B. 2
C. 3
D. 1

Solution

  1. Step 1: Perform unions step-by-step

    union(1, 2) merges sets {1} and {2} -> {1, 2}. union(3, 4) merges {3} and {4} -> {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

  2. Step 2: Find the representative of element 4

    After unions, all elements are in one set. The representative is usually the root of the first union, which is 1.

  3. Final Answer:

    1 -> Option D

  4. Quick Check:

    find(4) = 1 after unions [OK]
Hint: After unions, find returns the root representative [OK]
Common Mistakes:
  • Assuming find(4) returns 4 itself
  • Not merging sets correctly in union(2, 3)
  • Confusing element with its set representative
4. Given the following incorrect Disjoint Set code snippet, what is the main error?
def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        rootA = rootB  # Incorrect assignment
medium
A. The assignment does not update the parent of rootA
B. The find function is called incorrectly
C. The union function should return a value
D. The if condition should check rootA == rootB

Solution

  1. Step 1: Analyze the union operation

    The union operation should update the parent of one root to the other to merge sets.

  2. Step 2: Identify the error in assignment

    Assigning rootA = rootB only changes the local variable, not the parent array that tracks sets.

  3. Final Answer:

    The assignment does not update the parent of rootA -> Option A

  4. Quick Check:

    Union must update parent array, not local variables [OK]
Hint: Update parent array, not local variables [OK]
Common Mistakes:
  • Assigning roots instead of updating parent array
  • Confusing equality check in if condition
  • Expecting union to return a value
5. You have 5 elements {1, 2, 3, 4, 5} initially in separate sets. After performing union(1, 2), union(3, 4), and union(2, 3), which of the following statements is true?
hard
A. Elements 1 and 4 belong to the same set
B. Element 5 belongs to the same set as element 1
C. Elements 2 and 5 belong to the same set
D. All elements belong to the same set

Solution

  1. Step 1: Track unions step-by-step

    union(1, 2) merges {1, 2}. union(3, 4) merges {3, 4}. union(2, 3) merges sets containing 2 and 3 -> {1, 2, 3, 4}.

  2. Step 2: Check element 5's set

    Element 5 was never unioned, so it remains separate.

  3. Final Answer:

    Elements 1 and 4 belong to the same set -> Option A

  4. Quick Check:

    1 and 4 connected; 5 separate [OK]
Hint: Only unioned elements share sets; isolated remain separate [OK]
Common Mistakes:
  • Assuming all elements merge after some unions
  • Thinking element 5 is connected without union
  • Confusing which elements are merged
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard