990. Satisfiability of Equality Equations

Problem¶

Given equations between lowercase-letter variables using equality or inequality, determine whether all equations can hold simultaneously.

Input:  ["a==b", "b!=c", "c==a"]
State:  a == b == c, but b != c
Output: false

Key trick¶

Use disjoint-set union:

Merge every equality first.
Then reject any inequality whose variables belong to the same component.

Trap¶

Checking only direct equality misses transitive relationships such as a == b == c.
Processing inequalities before all equality components are complete can miss later contradictions.
a != a is always impossible.

Why is it interesting?¶

It turns logical equality into graph connectivity, showing how disjoint-set union efficiently maintains equivalence classes.

Python solution¶

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

        def find(x):
            # Path compression makes future lookups nearly constant time.
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a, b):
            root_a = find(a)
            root_b = find(b)
            if root_a != root_b:
                parent[root_a] = root_b

        # Build every equality component before checking inequalities.
        for eq in equations:
            if eq[1] == "=":
                a = ord(eq[0]) - ord("a")
                b = ord(eq[3]) - ord("a")
                union(a, b)

        for eq in equations:
            if eq[1] == "!":
                a = ord(eq[0]) - ord("a")
                b = ord(eq[3]) - ord("a")
                if find(a) == find(b):
                    return False

        return True

Time complexity: \(O(n \alpha(26))\), effectively \(O(n)\).

Space complexity: \(O(26)\), effectively \(O(1)\).

Comment on my solution¶

Your final graph-based solution is correct and handles both reported failing cases.

The colors values are component identifiers, not graph colors; component would be clearer terminology.
The early contradiction checks are unnecessary because the final traversal checks every stored inequality.
Disjoint-set union is shorter and directly models equality as an equivalence relation.
Splitting each four-character equation is less direct than reading eq[0], eq[1], and eq[3].

# Ideas:
# - build undirected graph where a==b represent edge between (a, b)
#   - when building it stop early returning False in b!=a found but
#     (a, b) already adjacent
# - color component with one color, if impossible return False
class Solution:
    def equationsPossible(self, equations: list[str]) -> bool:
        graph = {}
        disconnected = {}
        for eq in equations:
            adjacent = eq[1] == "="
            a, b = eq.split("==") if adjacent else eq.split("!=")
            if adjacent:
                if a in disconnected and b in disconnected[a]:
                    return False
                graph.setdefault(a, set()).add(b)
                graph.setdefault(b, set()).add(a)
            else:
                if a in graph and b in graph[a]:
                    return False
                if a == b:
                    return False
                disconnected.setdefault(a, set()).add(b)
                disconnected.setdefault(b, set()).add(a)

        colors = {}
        color = 0

        for start in graph:
            stack = [start]
            if start in colors:
                continue
            colors[start] = color
            while stack:
                node = stack.pop()
                for nei in graph[node]:
                    if nei not in colors:
                       colors[nei] = color
                       stack.append(nei)
                    elif colors[nei] != color:
                        return False
            color += 1

        for a in disconnected:
            for b in disconnected[a]:
                if a in colors and b in colors and colors[a] == colors[b]:
                    return False

        return True

Extra¶

Complement on DSU - disjoint-set union¶

This is the first time I learn about disjoint-set union. Can you explain it to me?

I seems that union creates a parent relationship between two nodes when they are not already part of a same component. Also find finds the root of a component, parent[root] = root. It seems that the last loop, check for nodes to be in different component. Your claim "Path compression makes future lookups nearly constant time." in find function is not obvious to me.

Is my understanding correct?

Your understanding is correct. The main missing idea is that DSU represents a partition into components, not a meaningful hierarchy.

What `parent` represents¶

Initially, every node is its own component and therefore its own root:

node:    a  b  c  d
parent:  a  b  c  d

A node is a root exactly when:

parent[root] == root

All nodes that eventually lead to the same root belong to the same component.

What `union` does¶

union(a, b) merges the components containing a and b.

It must connect their roots, not necessarily a directly to b:

root_a = find(a)
root_b = find(b)

if root_a != root_b:
    parent[root_a] = root_b

For example, after processing a == b and b == c, the structure might be:

a -> b -> c
          ^
          root

This means a, b, and c are in the same component. The direction of the arrows has no meaning beyond representing membership.

What `find` does¶

find(x) follows parent links until it reaches the root:

find(a): a -> b -> c
                     return c

Therefore:

find(a) == find(c)

means that a and c belong to the same equality component.

What path compression does¶

Without path compression, repeated calls to find(a) must repeatedly traverse:

a -> b -> c -> d

This line performs path compression:

parent[x] = find(parent[x])

While finding the root, it changes every visited node to point directly to that root.

Before find(a):

a -> b -> c -> d

After find(a):

a -> d
b -> d
c -> d
d -> d

Now future calls to find(a), find(b), or find(c) reach the root in one step.

The important point is that one find operation may still traverse several links, but it reorganizes the structure so later operations are much faster. “Nearly constant time” usually refers to the amortized cost across many operations.

Strictly speaking, the classic almost-constant \(O(\alpha(n))\) bound uses both:

Path compression.
Union by size or rank.

The earlier solution used only path compression. With only 26 possible variables, this distinction is practically irrelevant, but a standard DSU usually includes both optimizations.

Why inequalities are checked last¶

DSU records equalities only. It does not need to merge or otherwise store inequalities.

After all equalities have been processed, an inequality such as a != c is impossible exactly when:

find(a) == find(c)

For example:

a == b
b == c
a != c

The equalities place all three variables in one component:

find(a) == find(b) == find(c)

The final inequality requires a and c to have different values, so the equations are contradictory.

If their roots differ, the components can be assigned different integers.

Standard DSU with both optimizations¶

parent = list(range(26))
size = [1] * 26


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


def union(a: int, b: int) -> None:
    root_a = find(a)
    root_b = find(b)

    if root_a == root_b:
        return

    # Attach the smaller tree below the larger tree.
    if size[root_a] < size[root_b]:
        root_a, root_b = root_b, root_a

    parent[root_b] = root_a
    size[root_a] += size[root_b]

Union by size prevents tall trees from forming, while path compression flattens any remaining paths during find. Together, they make DSU operations amortized \(O(\alpha(n))\), which is effectively constant for realistic input sizes.