Problem Statement
Satisfiability of Equality Equations
You get a list of short strings called equations. Each one is exactly 4 characters long and says one of two things: two variables are equal, like 'a==b', or two variables are not equal, like 'a!=b'. The variables are single lowercase letters. Your job is to decide if there is some way to pick numbers for these letters so that every statement is true at once. If a way exists, return true. If the statements contradict each other, return false. The plan is simple: first read all the "equal" statements and put letters that must be the same into the same group, then read all the "not equal" statements and make sure no rule asks two letters in the same group to be different.
Signals to notice
Brute force first
Try all possible value assignments — exponential. Each variable could take any value. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Union-Find: first, process all equalities (union a and b). Then check all inequalities — if a!=b but find(a)==find(b), it's unsatisfiable. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on equations = ["a==b","b!=a"]
Init: parent[i]=i for all 26 letters (a=0..z=25), rank all 0 Pass 1 (only '==' eqs) — eq="a==b": eq[1]='=', union(0,1) union: roots 0,1 differ, ranks equal → parent[1]=0, rank[0]=1. Now a,b share root 0 Pass 2 (only '!=' eqs) — eq="b!=a": eq[1]='!', compute find(1) and find(0) find(1): parent[1]=0 → returns 0. find(0): returns 0. 0 == 0 → contradiction Return False (b is forced equal to a by group, but b!=a required)
What must stay true
Equality is transitive (a==b, b==c ⟹ a==c), making Union-Find natural. After merging all equal variables, any inequality between two variables in the same set is a contradiction. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
parent[i] = i for i in 0..25; rank[] = 0
for eq in equations: # PASS 1: unions
if eq[1] == '=': union(eq[0], eq[3])
for eq in equations: # PASS 2: check
if eq[1] == '!' and find(eq[0]) == find(eq[3]): return false
return truePseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Processing inequalities before equalities — equalities must be processed first because they constrain which variables must be equal. Then inequalities check for contradictions. The fix is usually to return to the meaning of each move, not just the steps themselves.