9 views
# Union Find Connected (Practice 4259): Notes Interviewers love union find connected because it checks whether you can state the invariant before coding. Here is a compact rehearsal note. ## Approach Path-compressed parents; unite by rank. ```python class DSU: def __init__(self, n): self.p = list(range(n)); self.r = [0]*n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.r[a] < self.r[b]: a, b = b, a self.p[b] = a if self.r[a] == self.r[b]: self.r[a] += 1 return True ``` ## Complexity Linear in the dominant input size for the scan; heap/tree variants add a log factor. ## Interview pitfalls State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode. ## Practicing out loud Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [official website](https://www.linkjob.ai/).