Domain 2MediumMEDIUM

Satisfiability of Equality Equations

Uses Disjoint Set Union (DSU) to group variables connected by equality constraints and validates inequality constraints against these groups.

Domain: medium•Updated: 2026-09-05
#Union-Find#Disjoint Set Union#O(N)#Constant Space

Problem Breakdown

We are given a list of equations involving single-character lowercase English letters. Each equation is either an equality (a==b) or an inequality (a!=b). The goal is to determine if there exists any assignment of integer values that satisfies all constraints simultaneously.

Key Constraints:

  • Transitivity: If a == b and b == c, then a must equal c. Equality forms connected components (equivalence classes).
  • Inequality Check: An inequality (a != b) is only valid if a and b are in different equivalence classes. If they end up in the same class due to equality chains, a contradiction exists.

Intuition

A brute-force approach attempting all integer assignments is impossible because integers can be arbitrarily large; we care about relative values (equality vs inequality). The problem maps naturally to graph theory: variables are nodes, and == constraints define edges merging components.

Core Insight:

  1. Build Components: Use a Disjoint Set Union (DSU) structure where all equality (==) operations merge the sets of their respective variables.
  2. Validate Contradictions: After processing all equalities, iterate through inequality (!=) constraints. If two variables in an a != b constraint belong to the same set (connected component), it is impossible to satisfy both the implied equality chain and the explicit inequality. Return False. Otherwise, return True.

Approach

  1. Initialize DSU: Create a parent array for all lowercase letters (‘a’-‘z’), where each index initially points to itself (parent[i] = i). This represents that every variable is its own set leader initially.
  2. Process Equalities (Pass 1): Iterate through the equations list. For any equation containing '==', perform a union operation on the two variables involved. The union function finds their roots and links one root to another, merging the sets. Path compression is used in the find operation to keep tree height low.
  3. Process Inequalities (Pass 2): Iterate through equations again. For any equation containing '!=', check if the two variables share the same root using the find function. If they do, a contradiction exists; return False.
  4. Return Result: If all inequality checks pass without finding connected components that should be unequal, return True.

Complexity Analysis

  • Time Complexity: O(N⋅α(K))O(N \cdot \alpha(K)), where NN is the number of equations and α\alpha is the inverse Ackermann function (nearly constant). Since the alphabet size K=26K=26 is fixed, this simplifies to effectively linear time relative to input length: O(N)O(N).
  • Space Complexity: O(K)O(K) for the parent array where K=26K=26. This is considered constant space (O(1)O(1)) with respect to the number of equations.

Solution

class Solution:
    def equationsPossible(self, equations):
        # Initialize DSU structure with 26 nodes ('a' -> 0 to 'z' -> 25)
        parent = list(range(26))
        
        # Find function with path compression for efficiency
        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])
            return parent[i]
            
        # Union function to merge two sets
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
        
        # First pass: Process all equality constraints (==)
        for eq in equations:
            u = ord(eq[0]) - 97  # 'a' is ASCII 97
            v = ord(eq[3]) - 97
            
            if eq[1] == '=':
                union(u, v)
        
        # Second pass: Check all inequality constraints (!=) against the built structure
        for eq in equations:
            u = ord(eq[0]) - 97
            v = ord(eq[3]) - 97
            
            if eq[1] == '!':
                # If 'u' and 'v' are already connected, this inequality is impossible to satisfy
                if find(u) == find(v):
                    return False
                    
        return True

# Example usage:
# sol = Solution()
# print(sol.equationsPossible(["a==b","b!=c"])) 

Edge Cases Handled

  • Self-Equality ("c==c"): The union function handles this gracefully; finding the root of ‘c’ twice results in no change, which is correct.
  • Redundant Equalities: Multiple "a==b", "b==a" are handled by DSU’s idempotent nature (merging already merged sets does nothing).
  • Contradictory Inequalities ("a!=c" where a and c become connected via other equations): The second pass explicitly checks if inequality nodes share a root. If they do, it returns False.
  • Disconnected Variables: Variables that never appear in any equation remain isolated (root = self), satisfying all constraints involving them trivially unless an explicit constraint links them to others.