Satisfiability of Equality Equations

medium graph union find

Problem

Given a list of equations a==b or a!=b over lowercase variables, return whether an assignment can satisfy them all.

Inputequations = ["a==b","b!=a"]

Outputfalse

First union '=='s, then check '!='s; any contradiction → false.

equations (comma list)

def equationsPossible(equations):
    parent = list(range(26))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for eq in equations:
        if eq[1] == '=':
            parent[find(ord(eq[0]) - 97)] = find(ord(eq[3]) - 97)
    for eq in equations:
        if eq[1] == '!':
            if find(ord(eq[0]) - 97) == find(ord(eq[3]) - 97): return False
    return True

function equationsPossible(equations) {
  const parent = Array.from({ length: 26 }, (_, i) => i);
  function find(x) { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
  for (const eq of equations) if (eq[1] === '=') parent[find(eq.charCodeAt(0) - 97)] = find(eq.charCodeAt(3) - 97);
  for (const eq of equations) if (eq[1] === '!') if (find(eq.charCodeAt(0) - 97) === find(eq.charCodeAt(3) - 97)) return false;
  return true;
}

class Solution {
    int[] parent = new int[26];
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < 26; i++) parent[i] = i;
        for (String eq : equations) if (eq.charAt(1) == '=') parent[find(eq.charAt(0) - 'a')] = find(eq.charAt(3) - 'a');
        for (String eq : equations) if (eq.charAt(1) == '!') if (find(eq.charAt(0) - 'a') == find(eq.charAt(3) - 'a')) return false;
        return true;
    }
}

int parent[26];
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
bool equationsPossible(vector<string>& equations) {
    for (int i = 0; i < 26; i++) parent[i] = i;
    for (auto& eq : equations) if (eq[1] == '=') parent[find(eq[0] - 'a')] = find(eq[3] - 'a');
    for (auto& eq : equations) if (eq[1] == '!') if (find(eq[0] - 'a') == find(eq[3] - 'a')) return false;
    return true;
}

Explanation

Equality is "sticky": if a == b and b == c, then a, b, c must all be equal. That grouping behavior is exactly what Union-Find models, so we put all variables that must be equal into the same group, then check the inequalities don't contradict.

There are only 26 lowercase letters, so parent is an array of size 26 where each letter starts in its own group. The find helper returns the root of a letter's group, and two letters are equal exactly when they share a root.

We do two passes. Pass one handles every == equation by unioning the two letters' groups. Pass two handles every != equation: if the two letters have the same root, they were forced equal yet must differ, which is impossible, so we return false.

Example: ["a==b","b!=a"]. Pass one unions a and b. Pass two sees b != a, but a and b now share a root, so it's a contradiction and the answer is false.

Doing all the == unions first matters: it ensures every equality is fully merged before we test any inequality, so transitive chains are handled correctly.

Time: O(n α(26)) Space: O(26)