LeetCode 990 - Satisfiability of Equality Equations

Difficulty: 🟡 Medium
Topics: Array, String, Union-Find, Graph Theory

Solution

Problem Understanding

The problem is asking us to determine if a set of equations between single-letter variables can all be satisfied simultaneously. Each equation is either of the form "xi==yi" or "xi!=yi", where xi and yi are lowercase letters from 'a' to 'z'. The task is to assign an integer value to each variable such that all equality (==) and inequality (!=) constraints hold true. If this is possible, we return true; otherwise, we return false.

The input is a list of strings, each exactly 4 characters long. The first and last characters represent the variables, while the middle two characters indicate the type of relationship. The constraints ensure that the number of equations is at most 500, which is small enough for a union-find or graph-based solution but likely too large for a brute-force approach that tries all possible variable assignments explicitly.

Edge cases include equations where a variable is compared to itself, such as "a==a" or "b!=b". The first is always satisfied, while the second is impossible and should immediately return false. Another subtle case is when inequalities contradict chains of equalities, like ["a==b", "b==c", "a!=c"], which cannot be satisfied. The problem guarantees that all input strings are valid equations, so no additional input validation is needed.

Approaches

The brute-force approach would attempt to assign integer values to variables in every possible combination, then check all equations. While correct in theory, this approach is infeasible due to the exponential number of possible assignments (26 variables with arbitrary integer assignments). Even reducing the range to a small set of integers is inefficient because the relationships create many dependent constraints, and checking all combinations grows exponentially with the number of variables.

The key insight for an optimal solution is to model the problem using the Union-Find (Disjoint Set Union) data structure. Variables connected by "==" form equivalence classes, which can be efficiently represented as connected components. After processing all equalities, we can then check each inequality to ensure that the two variables involved do not belong to the same component. If they do, the system of equations is unsatisfiable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26^N * N)	O(26)	Attempts all possible integer assignments for variables, exponential in the number of variables
Union-Find	O(N * α(N))	O(26)	Process equalities to build components, then verify inequalities; α(N) is inverse Ackermann function, practically constant

Algorithm Walkthrough

Initialize Union-Find: Create a parent array of size 26, one for each lowercase letter. Initially, each variable is its own parent.
Process Equalities: Iterate through the equations array. For each "xi==yi" equation, union the components of xi and yi. This step ensures that all variables that must be equal belong to the same connected component.
Process Inequalities: Iterate through the equations array again. For each "xi!=yi" equation, check if xi and yi belong to the same connected component using the find operation. If they do, return false immediately, because it is impossible to satisfy this inequality.
Return True: If no contradictions are found after processing all inequalities, return true.

Why it works: The union-find structure maintains the invariant that all variables in the same connected component are equal. By checking inequalities after building the components, we can efficiently determine whether any inequality is violated without trying all possible assignments.

Python Solution

from typing import List

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        parent = list(range(26))  # 'a' -> 0, 'b' -> 1, ..., 'z' -> 25

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

        def union(x: int, y: int):
            parent[find(x)] = find(y)

        # First, process all equalities
        for eq in equations:
            if eq[1:3] == "==":
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                union(x, y)

        # Then, check all inequalities
        for eq in equations:
            if eq[1:3] == "!=":
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                if find(x) == find(y):
                    return False

        return True

This implementation first sets up a union-find data structure for the 26 lowercase letters. Equalities are used to merge variable components, while inequalities are used to detect contradictions. Path compression ensures that the find operation runs nearly in constant time, keeping the overall algorithm efficient.

Go Solution

func equationsPossible(equations []string) bool {
    parent := make([]int, 26)
    for i := 0; i < 26; i++ {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) {
        parent[find(x)] = find(y)
    }

    // Process equalities first
    for _, eq := range equations {
        if eq[1:3] == "==" {
            x := int(eq[0] - 'a')
            y := int(eq[3] - 'a')
            union(x, y)
        }
    }

    // Check inequalities
    for _, eq := range equations {
        if eq[1:3] == "!=" {
            x := int(eq[0] - 'a')
            y := int(eq[3] - 'a')
            if find(x) == find(y) {
                return false
            }
        }
    }

    return true
}

The Go solution mirrors the Python implementation. One Go-specific difference is that slices are explicitly initialized and integer arithmetic is used to convert characters to indices. The union-find logic is identical, and path compression is applied recursively.

Worked Examples

Example 1: ["a==b","b!=a"]

Step	Action	Parent Array	Explanation
1	Initialize parent	`[0,1,2,...,25]`	Each variable is its own parent
2	Process "a==b"	`[1,1,2,...,25]`	Union a (0) and b (1), now a and b are connected
3	Check "b!=a"	`[1,1,2,...,25]`	Find(a) == Find(b) → contradiction, return False

Example 2: ["b==a","a==b"]

Step	Action	Parent Array	Explanation
1	Initialize parent	`[0,1,2,...,25]`	Each variable is its own parent
2	Process "b==a"	`[1,1,2,...,25]`	Union b (1) and a (0)
3	Process "a==b"	`[1,1,2,...,25]`	Already connected, no change
4	No inequalities	`[1,1,2,...,25]`	No contradictions, return True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N * α(N))	Each union/find operation is nearly constant due to path compression, where N is the number of equations
Space	O(26)	Only need a parent array for 26 lowercase letters

Because the number of variables is fixed at 26, the space complexity is effectively constant. Processing equalities and inequalities requires at most two passes through the equations array.

Test Cases

# Provided examples
assert Solution().equationsPossible(["a==b","b!=a"]) == False  # contradiction
assert Solution().equationsPossible(["b==a","a==b"]) == True   # consistent equalities

# Edge cases
assert Solution().equationsPossible(["a==a"]) == True           # variable equal to itself
assert Solution().equationsPossible(["a!=a"]) == False          # impossible inequality
assert Solution().equationsPossible(["a==b","b==c","c!=a"]) == False  # chain contradiction
assert Solution().equationsPossible(["a==b","b==c","c==d","d!=e"]) == True  # no contradiction
assert Solution().equationsPossible(["a!=b","b!=c","a==c"]) == False  # indirect contradiction

# Stress test
assert Solution().equationsPossible(["a==b"]*500) == True       # all equalities, large input

Test	Why
["a==b","b!=a"]	Tests direct contradiction
["b==a","a==b"]	Tests simple consistent equalities
["a==a"]	Self-equality, trivially true
["a!=a"]	Self-inequality, impossible