Satisfiability of Equality Equations: Union-Find for Variable Constraints

You are given an array of strings equations where each equation is four characters long: a lowercase variable, an operator (== or !=), and another lowercase variable. Determine whether it is possible to assign integers to the variable names so that all the equations are satisfied simultaneously.

This is LeetCode 990: Satisfiability of Equality Equations. For example, ["a==b", "b!=a"] is unsatisfiable because a must equal b, yet the second equation says they differ. On the other hand, ["a==b", "b==c", "a==c"] is satisfiable since setting all three to the same value works.

The problem

Each equation tells you one of two things about a pair of variables: either they must have the same value, or they must have different values. You need to check whether all these constraints can hold at once.

The tricky part is transitivity. If a == b and b == c, then a == c must also hold. So when you later see a != c, you have a contradiction. Tracking which variables are transitively equal is the core challenge.

The brute force approach

One naive option is to build a graph of equality constraints and run a search (BFS or DFS) to figure out connected components. For every == equation, add an edge between the two variables. Then for every != equation, check whether both variables end up in the same connected component.

This works, but it requires building an adjacency list, running a traversal for each inequality check, and keeping track of visited nodes. The overhead adds up. There is a cleaner structure that handles exactly this type of "group things together, then query group membership" pattern.

The key insight

Equality is an equivalence relation: it is reflexive, symmetric, and transitive. Union-find is purpose-built for equivalence relations. You union two variables when they must be equal, and you query their roots when you need to check whether two variables are in the same group.

The algorithm has two passes. First, process every == equation by calling union(a, b). This groups all transitively equal variables together. Second, process every != equation by calling find(a) and find(b). If they share the same root, you have a contradiction and return false. If you get through all inequality checks without a conflict, return true.

Step-by-step walkthrough

Let's trace through ["a==b", "b==c", "a!=c"] and watch the union-find data structure evolve.

The code

def equationsPossible(equations):
    parent = list(range(26))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py

    for eq in equations:
        if eq[1] == '=':
            union(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a'))

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

    return True

The parent array has 26 entries, one for each lowercase letter. The find function uses path compression (pointing each node to its grandparent as it traverses upward) to keep the tree flat. The union function connects two roots.

The first loop handles all == equations. We check eq[1] == '=' because the operator is either == or !=, so looking at the second character is enough to distinguish them. The second loop handles all != equations, checking whether the two variables share a root.

Complexity analysis

Here n is the number of equations and V is the number of distinct variables (at most 26). The inverse Ackermann function alpha(V) is effectively constant, so the union-find approach runs in O(n) time. Space is O(V) for the parent array, which is O(1) when V is bounded by 26.

The building blocks

Union-find for equivalence grouping

Union-find excels whenever you need to group elements by an equivalence relation and later query whether two elements belong to the same group. The "union on one condition, then query on another" two-pass pattern is reusable: group things together first, then validate constraints against those groups. You will see it again in problems like connected components, cycle detection, and account merging.

Two-pass constraint checking

Processing all "positive" constraints before checking "negative" constraints is a pattern that shows up beyond union-find. Any time you have constraints that build structure (equalities, connections, memberships) mixed with constraints that test structure (inequalities, separations, exclusions), handle the building phase first. This guarantees that when you validate, your data structure reflects the complete picture.

Edge cases

• All equalities, no inequalities. Every variable can have the same value. Always return true.
• Single variable inequality like "a!=a". After the union pass, find(a) == find(a) is always true, so this correctly returns false.
• No equations at all. The input is empty. No constraints means no contradictions. Return true.
• Disconnected groups with inequalities between them. For example, ["a==b", "c==d", "a!=c"]. The groups {a,b} and {c,d} are separate, so a != c is satisfiable. Return true.

From understanding to recall

You just walked through the two-pass union-find pattern: union all equalities first, then check all inequalities for contradictions. The algorithm is short, but remembering the two-pass structure, the find with path compression, and the ord conversions under pressure takes practice.

Spaced repetition locks it in. You write the solution from scratch after a day, then three days, then a week. Each time, you rebuild the parent array, the find and union helpers, and the two loops. After a few rounds, the pattern becomes automatic and you start recognizing it in other problems that involve grouping and constraint validation.

Related posts

• Number of Provinces - Another union-find problem grouping connected components
• Redundant Connection - Uses union-find to detect cycles in an undirected graph
• Accounts Merge - Groups accounts by common emails using union-find