Satisfiability of Equality Equations
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.
- 1 <= equations.length <= 500
- equations[i].length == 4
- equations[i][0] is a lowercase letter.
- equations[i][1] is either '=' or '!'.
- equations[i][2] is '='.
- equations[i][3] is a lowercase letter.
Intuition
Satisfiability of equality equations takes constraints like "a==b" and "a!=b" and asks whether integers can be assigned to satisfy all of them at once.
The property that shapes the solution is that equality is transitive. If a == b and b == c, then a == c follows whether or not it was stated. So the equalities partition the variables into groups that must all hold the same value.
Grouping under transitive merging is precisely what Union-Find does, and each group is one connected component.
Inequality is not transitive — a != b and b != c say nothing about a and c — so the two kinds of constraint must be handled differently, and the order matters:
- Process every equality first, merging groups; only then check the inequalities against the finished groups.
If an inequality were checked before all equalities were processed, two variables might not yet be merged and a genuine contradiction would slip through. Doing all the merging first means each group is final when tested.
Then every a != b is a single question: are a and b in the same group? If they are, they are forced equal and forced unequal simultaneously — a contradiction, so return false.
The variable space is tiny: single lowercase letters, so at most 26 elements. A fixed parent array of size 26 is all the structure needed.
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
Before reading on: price up what the direct approach costs here, then ask whether you are really just merging groups and asking what connects. Aim for O(n) time and O(1) space.
Note that equality is transitive
a == b and b == c imply a == c. The equalities partition variables into groups that must share a value, which is exactly what Union-Find models.
Size the structure at 26
Variables are single lowercase letters, so a fixed parent array of 26 entries covers every possibility. No hashing or dynamic allocation is needed.
Process all equalities first
Scan for == equations and union the two variables. Every merge must be complete before any inequality is checked — testing early could miss a contradiction that a later merge would have created.
Then check every inequality
For each != equation, test whether the two variables share a root. The same root means they are forced equal and forced unequal at once — a contradiction, so return false.
Return true if nothing contradicts
If every inequality passes, a valid assignment exists — give each group a distinct integer. The problem asks only whether one exists, so no assignment need be constructed.
Apply the Union-Find optimisations
Path compression and union by rank keep operations near-constant. With only 26 elements the practical difference is small, but the habit matters on larger inputs.
Cost of the two passes
Both passes are linear in the number of equations with near-constant Union-Find operations, giving O(n · α(n)) time — effectively linear — and O(1) space, since the parent array is a fixed 26 entries.
Solution & live demo
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.