Satisfiability of Equality Equations
Given an array of equations like "a==b" and "a!=b", return true if it is possible to assign integers to the variables so that all equations are satisfied simultaneously.
Intuition
Equality is transitive: if a == b and b == c, then a == c. This is exactly what Union-Find models — merge variables that must be equal. Process all == equations first, unioning the two variables. Then check all != equations: if the two variables in a != equation are in the same connected component, they were forced to be equal by some chain of == equations, and the system is unsatisfiable. If no != conflicts with the components, return true.
When a problem gives you a set of 'same' and 'different' constraints and asks if they are consistent, the shape is Union-Find: merge 'same' pairs, then check if any 'different' pair ended up merged. The key is processing equalities first. This pattern extends to any equivalence-class consistency check — connected components, friend/enemy networks, bipartite checks.
Approach
Build a Union-Find over the 26 possible variables
Each variable is a single lowercase letter, so there are at most 26. Initialize a parent array of size 26 where parent[i] = i. Implement find with path compression and union by rank for efficiency.
Process all equality equations first, merging variables
Scan the equations and pick out those with ==. For each, union the two variables. After this pass, all variables forced to be equal are in the same component.
Check inequality equations against the merged components
Scan the equations again and pick out those with !=. For each, check if find(a) == find(b). If so, the equality chain contradicts the inequality — return false. If no conflict is found, return true. Time is O(n * α(26)) ≈ O(n). Space is O(26) = O(1).
Solution
Common pitfalls
Processing != and == equations in a single pass
for eq in equations:
if eq[1] == '=':
union(eq[0], eq[3])
else:
if find(eq[0]) == find(eq[3]):
return Falsefor eq in equations:
if eq[1] == '=':
union(eq[0], eq[3])
for eq in equations:
if eq[1] == '!':
if find(eq[0]) == find(eq[3]):
return FalseProcessing in one pass means some == equations have not been applied when a != is checked. A later == might merge the two variables, but the != check already passed without detecting the conflict. All unions must happen before any inequality check.
Using the character directly instead of converting to an index
parent[eq[0]] = eq[0]
parent[ord(eq[0]) - ord('a')] = ord(eq[0]) - ord('a')The parent array is indexed 0–25 for letters a–z. Using the character itself as an index causes a TypeError in Python or an out-of-bounds access in other languages.
Not implementing path compression in find
def find(x):
while parent[x] != x:
x = parent[x]
return xdef find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Without path compression, long chains degrade find to O(n). With it, amortised cost is nearly O(1). For 26 variables the difference is negligible, but it is a correctness habit that matters on larger inputs.
Edge cases
"a!=a"find(a) == find(a) is always true, so this immediately returns false. A variable cannot be unequal to itself.
There is nothing to contradict. Return true.
Every variable is in its own component. A != equation between two different variables is always satisfiable. Return true unless there is a self-inequality.