Satisfiability of Equality Equations

Problem

You are given a list of equations like "a==b" and "a!=b" where each variable is a single lowercase letter. Determine if all equations can be satisfied simultaneously. An == equation is a contradiction if the same two variables later appear in a != equation.

["a==b","b!=c","c==a"]  →  False
["c==c","b==d","x!=z"]  →  True
["a==b","b!=a"]         →  False

Solution

Approach - Two-pass Union-Find: union all equalities, then verify every inequality.

Variables are single lowercase letters, so the whole universe is 26 nodes - a fixed parent = list(range(26)) indexed by ord(c) - ord('a'), which is why the structure stays O(1) space regardless of how many equations arrive. The insight is that order of passes matters. Equality is transitive: a == b and b == c force a == c. If we checked a != constraint before every == had been applied, two variables that a later equality would connect could wrongly pass the inequality test. So pass one scans every equation and, for the equalities (detected by eq[1] == '='), unions the two variables, building the full set of forced-equal components. Only then does pass two scan the inequalities (eq[1] == '!'): for each a != b, if find(a) == find(b) the two are forced equal and forced unequal at once - an unsatisfiable contradiction, so we return False. Surviving both passes means every constraint holds, so return True.

Trace ["a==b","b!=c","c==a"]: pass one unions a~b and c~a, so a, b, c all share a root. Pass two hits b != c, finds find(b) == find(c), and returns False.

Edge cases - a == a is a harmless no-op union. a != a always contradicts, since find(a) == find(a) is trivially true, correctly returning False.

Complexity - O(n * alpha(26)) which collapses to O(n) time for n equations. O(1) space - the arrays are fixed at 26.