Skip to main content

990 - Satisfiability of Equality Equations

Difficulty: Medium | Pattern: Union-Find | Company tags: Google, Amazon, Facebook

Problem Statement​

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two forms: "xi==yi" or "xi!=yi". Here, xi and yi are lowercase letters (not necessarily different).

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Example 1:

Input: equations = ["a==b","b!=a"]
Output: false  (a==b and b!=a is a contradiction)

Example 2:

Input: equations = ["b==a","a==b"]
Output: true  (a and b can be the same value)

Approach: Union-Find — O(n α(n)), O(1)​

Key insight:

  1. Process all == equations first — union those variables.
  2. Then check all != equations — if both variables have the same root, contradiction.
def equationsPossible(equations: list[str]) -> bool:
    parent = list(range(26))
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    # Pass 1: union all equal pairs
    for eq in equations:
        if eq[1] == '=':
            union(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a'))
    
    # Pass 2: check inequality pairs
    for eq in equations:
        if eq[1] == '!':
            a, b = ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a')
            if find(a) == find(b):
                return False
    
    return True

Algorithm Flow​

Dry Run​

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

  • Union 'a' and 'b' (eq[1]='=') → parent['a'] = 'b'
  • Check 'b' != 'a' → find('b')='b', find('a')='b' → same root → return False ✓

Why Two Passes?​

A single pass might see a!=b before processing a==c and b==c, missing the transitive equality. Processing all == first ensures the union-find reflects all equalities before inequality checks.

Complexity​

  • Time: O(n α(n)) ≈ O(n) amortized
  • Space: O(1) (26-element array)

Key Terms​

TermDefinition
Union-Find (DSU)Data structure tracking disjoint sets of connected variables, supporting find and union operations.
Path compressionOptimization in find that rewires nodes directly to a shallower ancestor, flattening future lookups.
Amortized inverse-Ackermann O(α(n))Near-constant time complexity per find/union call once path compression (and/or union by rank) is applied.
Two-pass processingApplying all equality constraints before inequality checks so transitive equalities are fully resolved first.
Root/representativeThe canonical element (find(x)) identifying which connected component x belongs to.

FAQ​

  1. Can this be solved without Union-Find? Yes — build a graph where == edges connect variables, run BFS/DFS to find connected components, then check every != pair doesn't share a component; this is O(n) but more code than DSU.
  2. What if the input has no != equations? Every consistent assignment works (just union all == pairs); the function returns True immediately since pass 2 never triggers a contradiction.
  3. How would this change if variables were uppercase and lowercase letters (52 symbols)? Size the parent array to 52 and map each character to an index accordingly; the algorithm logic is unchanged.
  4. Why must all == equations be processed before any != check? An inequality like a!=b could be a false contradiction if a later equality chain (e.g. a==c, c==b) would actually force a==b; processing unions first captures all transitive equalities.
  5. What about self-referential equations like "a==a" or "a!=a"? "a==a" is a no-op union; "a!=a" is always a contradiction since find(a) == find(a) trivially, so the function correctly returns False.

Quick Revision​

  • Model each equation as a union (==) or a same-set rejection (!=) over 26 lowercase-letter variables.
  • Pass 1: union all variables connected by == equations.
  • Pass 2: for every != equation, if both sides share a root, return False.
  • Path compression in find keeps lookups near O(1) amortized.
  • Order matters: unions must be fully applied before inequality checks to capture transitive equality.
  • No union by rank needed here since the domain is fixed at 26 elements — path compression alone suffices.
  • Time: O(n·α(26)) ≈ O(n); Space: O(1) for the fixed 26-slot parent array.
  • Contrast with graph-based components (BFS/DFS) which solve the same problem without a DSU structure.
  • 200 - Number of Islands — connected-components pattern solvable with Union-Find or BFS/DFS.
  • Pattern match: "Redundant Connection" (LeetCode 684) — classic Union-Find cycle-detection problem (create if the file exists in this directory).
  • Pattern match: "Accounts Merge" (LeetCode 721) — Union-Find over string keys instead of fixed-size alphabet indices.