Satisfiability of Equality Equations
Problem Statement
You are given an array of equations over lowercase variables a through z. Each equation has the form x==y or x!=y.
Return true if it is possible to assign values to the variables so that every equation is satisfied. Otherwise return false.
Input
An array equations of equality and inequality strings over 26 lowercase variables.
Output
A boolean: true if all equations can be satisfied at the same time, otherwise false.
Constraints
- •
1 <= equations.length <= 500 - •
equations[i].length == 4 - •
equations[i][0] and equations[i][3] are lowercase English letters - •
equations[i][1] is '=' or '!' - •
equations[i][2] is '='
Examples
Example 1
equations = ["a==b","b!=c","c==a"]
falseExample 2
equations = ["a==b","b==c","a==c","x!=y"]
trueLearning Objectives
- Use DSU to represent equivalence classes created by equality constraints.
- Separate positive constraints from negative constraints with a two-pass algorithm.
- Recognise contradictions by checking whether an inequality falls inside one DSU component.
Intuition
Equality is transitive. If a==b and b==c, then a, b, and c must all live in the same equivalence class. Union-Find is a natural fit because it maintains exactly those classes.
Inequality is different: a!=b does not tell us where either variable belongs; it only forbids them from ending up in the same class. That is why the order matters. First process every equality so all forced classes are complete. Then scan inequalities and reject any one whose two variables now share a root.
This two-pass structure is the whole problem. If you check inequalities too early, you may miss a later equality that creates the contradiction.
Common mistakes
- ×Processing equations in input order and accepting an inequality before all equalities have been unioned.
- ×Checking the wrong character for the operator. The operator is determined by index 1.
- ×Forgetting that x!=x is immediately impossible because both sides have the same root.
- ×Using 500 DSU nodes for equations instead of 26 nodes for variables.
- ×Treating inequality as a union operation. Inequality is a check, not a merge.
Algorithm Explanation
- Create a Union-Find of size 26, one node for each lowercase variable.
- First pass: for every equation whose operator is equality, union the two variables.
- Second pass: for every inequality, compare the roots of its two variables. If the roots are equal, the constraints contradict each other, so return false.
- If no inequality is violated, return true.
Solutions
Solution: Two-pass Union-Find
Use this for equality and inequality constraint systems where positive constraints form equivalence classes and negative constraints only need contradiction checks.
Union every equality first, then verify each inequality against the finished DSU. With only 26 variables, the implementation is small, but the pattern scales to larger symbolic constraint problems.
Step-by-step
- Convert a variable to an id by subtracting a.
- In the equality pass, union the ids at positions 0 and 3 whenever position 1 is equality.
- In the inequality pass, if those same two ids have the same root, return false immediately.
- Reaching the end means no forbidden pair was forced equal.
O(m · α(26))
O(26)
m is the number of equations. Because there are only 26 variables, this is effectively linear time and constant space.
Java implementation
Dry Run
Sample input
equations = [a==b, b!=c, c==a]. First finish all equality unions, then check inequalities.
| Pass | Equation | DSU state | Decision |
|---|---|---|---|
| Equality | a==b | {a,b} plus other singletons | merge a and b |
| Equality | b!=c | unchanged | skip until inequality pass |
| Equality | c==a | {a,b,c} plus other singletons | merge c into a's set |
| Inequality | b!=c | b and c have same root | contradiction, return false |
The inequality looks harmless before c==a is processed, but after all equalities are complete, b and c are in the same equivalence class. That makes b!=c impossible.
Interview Tips
Emphasise the two-pass reason, not just the mechanics. Equalities create facts; inequalities validate against the final facts. This framing prevents the common input-order bug and makes the proof simple: after pass one, DSU contains exactly the forced equality classes; pass two checks that no forbidden pair lies inside a class.
Likely follow-ups
- What if variables are arbitrary strings instead of 26 lowercase letters? Map each string to an id as in Accounts Merge.
- What if equations include less-than constraints? DSU alone is not enough; you need ordering constraints and cycle detection.
- Return one concrete assignment of integer values. Give each DSU component a distinct value, then verify inequalities.
- Support online additions and report when a contradiction first appears. Union equalities as they arrive, but store inequalities for rechecking or use a richer dynamic structure.
Similar Problems
Key Takeaways
- Union-Find models equality as connected components or equivalence classes.
- Negative constraints are checked after all positive constraints are known.
- Inequality never unions nodes; it rejects two nodes that already share a root.
- Small fixed alphabets still benefit from the DSU pattern because the reasoning is clear and scalable.