Satisfiability of Equality Equations

Problem

You are given a list of equations like "x==y" and "m!=n" 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.

Example 1:

Input: equations = ["x==y","y!=z","z==x"]
Output: False
Explanation: x==y and z==x force x, y, and z to be equal, but y!=z contradicts that.

Example 2:

Input: equations = ["p==p","q==r","m!=n"]
Output: True
Explanation: no inequality conflicts with a forced equality, so all equations can hold.

Example 3:

Input: equations = ["x==y","y!=x"]
Output: False
Explanation: x==y and y!=x directly contradict each other.

Constraints:

• 1 <= equations.length <= 300
• 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.

Solution Breakdown

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 ["x==y","y!=z","z==x"]: pass one unions x~y and z~x, so x, y, z all share a root. Pass two hits y != z, finds find(y) == find(z), and returns False.

Edge cases - m == m is a harmless no-op union. m != m always contradicts, since find(m) == find(m) 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.