← DSA Atlas
Dedicated problem page · #990

Satisfiability of Equality Equations

MediumUnion-Find / Disjoint Set UnionEquality classes then contradiction checkUnion-Find over 26 variables
Solve on LeetCode ↗
990
MediumUnion-Find / Disjoint Set UnionUnion-Find over 26 variablesEquality classes then contradiction check

Satisfiability of Equality Equations

You are given equations of the form "a==b" or "a!=b", where each side is a single lowercase letter variable. Return true if it is possible to assign integer values to the variables so that all equations hold, and false otherwise.

Open official problem prompt ↗
In plain English

Decide whether a set of equality and inequality constraints over letter variables is jointly satisfiable.

Picture it like this

Group people who must sit together (==), then check no 'must sit apart' rule (!=) applies to two people already forced into the same group.

Example
Input
equations = ["a==b","b!=a"]
Output
false
Why
a==b forces a and b to be equal, but b!=a demands they differ, which is impossible.
Constraints
1 <= equations.length <= 500equations[i].length == 4equations[i][0] and equations[i][3] are lowercase lettersequations[i][1] is '=' or '!'equations[i][2] is '='
Pattern lesson

See the pattern, then code

Equality classes then contradiction check
Recognition clue

Equality is transitive and symmetric, forming equivalence classes; then inequalities must not contradict them. Building equivalence classes and testing constraints is a textbook two-phase Union-Find.

↗
Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Process all '==' equations first to merge variables into equality classes. Then for each '!=' equation, if both sides are already in the same class the constraints conflict; if none conflict, a valid assignment exists.

New words, made simpleKnow these before the algorithm
Equivalence class
A set of variables all forced to be equal by == constraints.
Two-phase processing
Handle all equalities first, then validate inequalities against the finished classes.
Contradiction
An a!=b where a and b were already merged, making satisfaction impossible.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try all assignments

Infeasible; the value space is unbounded and combinatorial.

Brute-force assign small integers to each variable and test all equations.

Time exponentialSpace O(1)
Best choiceUnion-Find equality classes

Linear, exact, and only 26 possible variables.

Merge on ==, then reject if any != links two already-merged variables.

Time O(n α(26))Space O(1)
The rule we keep true

Invariant

After phase 1, two variables share a root if and only if the == equations force them to be equal.

Why this is correct

Reasoning

Equality is an equivalence relation, so == constraints partition the variables into classes that must take one value each. Any != between variables in different classes is satisfiable by giving classes distinct values. The only obstruction is an != within a single class, so checking for exactly that is both necessary and sufficient.

The algorithm in three movesSay these aloud before coding
1Create a DSU over the 26 letters

phase 1: union(a,b) -> {a,b}

2For every '==' equation, union the two variables

phase 2: b!=a?

3For every '!=' equation, check the two variables are in different sets

find(b)==find(a) -> conflict

4Return false on the first conflict, otherwise true

return False

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
a0
==1
b2
!=3
1 · Read"a==b"
2 · AskUnion?
3 · Update stateparent[find(a)]=find(b)
4 · Resulta and b share a root
Key takeaway

a and b merge in phase 1; the phase-2 inequality then finds them in the same set.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 326-slot DSU

    One parent slot per lowercase letter, indexed by ord(c) - 97.

  2. 2
    Lines 11-13Phase 1 unions

    Process only '==' equations so equality classes are complete before any check.

  3. 3
    Lines 15-18Phase 2 checks

    For each '!=', a shared root means an impossible constraint, so return False.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Self-equality like "a==a" is always fine
  • Self-inequality like "a!=a" is always false (same variable, same root)
  • All equalities with no inequalities is always true
!

Common beginner mistakes

  • Interleaving == and != in one pass, so a later == silently satisfies an earlier != you already accepted
  • Indexing letters incorrectly (must subtract ord('a'))
  • Missing the self-inequality "a!=a" case, which the same-root check handles automatically
Check your understanding

Why must all '==' equations be processed before any '!=' check?

More in Union-Find / Disjoint Set Union

#684Redundant ConnectionCycle detection while building#305Number of Islands IIIncremental connectivity#721Accounts MergeMerge by shared key#947Most Stones Removed with Same Row or ColumnConnected components, keep one per group#952Largest Component Size by Common FactorUnion by prime factors#1319Number of Operations to Make Network ConnectedCount components, connect with spare edges