Skip to interview prep
Apexed

210. What is an equivalence relation, and how does it relate to disjoint sets?

EasyDisjoint sets

Technical
Show model answer

A relation R is an equivalence relation if it is reflexive (a R a), symmetric (a R b implies b R a) and transitive (a R b and b R c imply a R c). Examples: being in the same connected component, having the same remainder mod m, or being the same person in deduplicated records.

An equivalence relation partitions its elements into disjoint equivalence classes. The union-find (disjoint set) structure maintains exactly such a partition dynamically: union merges two classes when a new equivalence is learned, and find returns a canonical representative so two elements are equivalent if and only if they have the same representative.

What is an equivalence relation, and how does it relate to disjoint sets — Data structures & algorithms interview question — Apexed