# 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:

```python
"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:

```python
["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

| Item | Meaning |
|---|---|
| Input | List of equation strings |
| Output | Boolean |
| Equality | `"x==y"` means `x` and `y` must be in the same group |
| Inequality | `"x!=y"` means `x` and `y` must be in different groups |
| Variables | Lowercase English letters |

Function shape:

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

## Examples

Example 1:

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

The first equation requires:

```python
a == b
```

The second equation requires:

```python
b != a
```

These conflict.

Answer:

```python
False
```

Example 2:

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

Both equations say the same relationship.

Answer:

```python
True
```

Example 3:

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

All three variables can have the same value.

Answer:

```python
True
```

Example 4:

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

From equality equations:

```python
a == b
c == a
```

So:

```python
a == b == c
```

But the inequality says:

```python
b != c
```

This is impossible.

Answer:

```python
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:

```python
"a==b"
"b!=a"
```

we can return `False`.

But this is not enough.

The conflict may be indirect:

```python
["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:

```python
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:

| Operation | Meaning |
|---|---|
| `find(x)` | Return the group representative of `x` |
| `union(x, y)` | Merge the groups of `x` and `y` |

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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n α(26))` | Each equation uses union-find operations |
| Space | `O(1)` | There are always only `26` lowercase variables |

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

## Implementation

```python
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:

```python
parent = list(range(26))
```

Each variable starts as its own parent.

The `find` function returns the representative of a group:

```python
def find(x: int) -> int:
```

Path compression makes future lookups faster:

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

The `union` function merges two equality groups:

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

The first pass handles equality equations:

```python
if equation[1] == "=":
```

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

We convert letters to indices:

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

Then merge their groups:

```python
union(x, y)
```

The second pass handles inequality equations:

```python
if equation[1] == "!":
```

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

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

If all inequalities pass, the equations can be satisfied:

```python
return True
```

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `["a==b", "b!=a"]` | `False` | Direct contradiction |
| `["b==a", "a==b"]` | `True` | Repeated equality |
| `["a==b", "b==c", "a==c"]` | `True` | Transitive equality is consistent |
| `["a==b", "b!=c", "c==a"]` | `False` | Indirect contradiction |
| `["c==c", "b==d", "x!=z"]` | `True` | No conflict |
| `["a!=a"]` | `False` | A variable cannot differ from itself |
| `["a==b", "b==c", "c!=a"]` | `False` | Inequality conflicts with equality group |