Medium · Two-Pass DSU
Understand → Visualise → Practice.
Variables are lowercase letters. Return whether all equality and inequality equations can hold simultaneously.
Equalities are transitive, so union all letters joined by ==. Then every != equation must join letters in different sets.
For every "x==y", union x and y.
For every "x!=y", if x and y share a root, the system is impossible.
Return true if no inequality is violated.
O(n α(26)) time and O(1) space for 26 letters.
Checking inequalities before all equalities are merged can miss a contradiction found later.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.