LeetCode 990: Satisfiability of Equality Equations

Problem Restatement

We are given an array of equations.

Each equation has exactly four characters and is one of two forms:

"a==b"
"a!=b"

Each variable is a lowercase English letter.

We need to return True if it is possible to assign integer values to the variables so that all equations are satisfied. Otherwise, return False.

For example:

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

cannot be satisfied, because the first equation says a and b must be equal, while the second says they must be different.

The official problem asks whether all equality and inequality equations can be satisfied simultaneously.

Input and Output

Function shape:

def equationsPossible(equations: list[str]) -> bool:
    ...

Examples

Example 1:

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

The first equation requires:

a == b

The second equation requires:

b != a

These conflict.

Answer:

False

Example 2:

equations = ["b==a", "a==b"]

Both equations say the same relationship.

Answer:

True

Example 3:

equations = ["a==b", "b==c", "a==c"]

All three variables can have the same value.

Answer:

True

Example 4:

equations = ["a==b", "b!=c", "c==a"]

From equality equations:

a == b
c == a

So:

a == b == c

But the inequality says:

b != c

This is impossible.

Answer:

False

First Thought: Compare Equations Directly

A direct approach is to check every pair of equations and try to detect conflicts.

For example, if we see:

"a==b"
"b!=a"

we can return False.

But this is not enough.

The conflict may be indirect:

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

There is no direct equation "a==c" at first, but equality is transitive.

If a == b and b == c, then a == c.

So we need a structure that can group variables connected by equality.

Key Insight

Equality equations form groups.

If:

a == b
b == c

then a, b, and c belong to the same group.

After building these groups, every inequality equation must connect two variables from different groups.

This is exactly what union-find does.

Union-find supports two operations:

Since variables are lowercase letters, we only need 26 nodes.

Algorithm

Use two passes.

First pass:

1. Process only equality equations.
2. For each equation "x==y", union x and y.

Second pass:

1. Process only inequality equations.
2. For each equation "x!=y", check whether x and y have the same root.
3. If they do, return False.

If no contradiction is found, return True.

Correctness

The first pass unions every pair of variables that must be equal. Because union-find merges connected components, variables connected by a chain of equality equations end up in the same group.

Therefore, after the first pass, two variables have the same root exactly when the equality equations require them to be equal.

The second pass checks every inequality equation. If an inequality equation says x != y, but x and y have the same root, then the equality equations force them to be equal. This is a contradiction, so no valid assignment exists.

If every inequality equation connects variables from different groups, then we can assign one integer value to each equality group. Different groups involved in inequality constraints can receive different values. All equality equations are satisfied inside groups, and all inequality equations are satisfied across groups.

Therefore, the algorithm returns True exactly when the equations are satisfiable.

Complexity

Let n = len(equations).

α is the inverse Ackermann function. With only 26 variables, this is effectively constant time.

Implementation

class Solution:
    def equationsPossible(self, equations: list[str]) -> bool:
        parent = list(range(26))

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            root_x = find(x)
            root_y = find(y)

            if root_x != root_y:
                parent[root_x] = root_y

        for equation in equations:
            if equation[1] == "=":
                x = ord(equation[0]) - ord("a")
                y = ord(equation[3]) - ord("a")
                union(x, y)

        for equation in equations:
            if equation[1] == "!":
                x = ord(equation[0]) - ord("a")
                y = ord(equation[3]) - ord("a")

                if find(x) == find(y):
                    return False

        return True

Code Explanation

We create 26 separate groups:

parent = list(range(26))

Each variable starts as its own parent.

The find function returns the representative of a group:

def find(x: int) -> int:

Path compression makes future lookups faster:

if parent[x] != x:
    parent[x] = find(parent[x])

The union function merges two equality groups:

def union(x: int, y: int) -> None:

The first pass handles equality equations:

if equation[1] == "=":

For "a==b", equation[0] is the first variable and equation[3] is the second variable.

We convert letters to indices:

x = ord(equation[0]) - ord("a")
y = ord(equation[3]) - ord("a")

Then merge their groups:

union(x, y)

The second pass handles inequality equations:

if equation[1] == "!":

If both variables have the same root, they are forced equal, so the inequality is impossible:

if find(x) == find(y):
    return False

If all inequalities pass, the equations can be satisfied:

return True

Testing

def run_tests():
    s = Solution()

    assert s.equationsPossible(["a==b", "b!=a"]) is False
    assert s.equationsPossible(["b==a", "a==b"]) is True
    assert s.equationsPossible(["a==b", "b==c", "a==c"]) is True
    assert s.equationsPossible(["a==b", "b!=c", "c==a"]) is False
    assert s.equationsPossible(["c==c", "b==d", "x!=z"]) is True
    assert s.equationsPossible(["a!=a"]) is False
    assert s.equationsPossible(["a==b", "b==c", "c!=a"]) is False

    print("all tests passed")

run_tests()