{x}
blog image

Satisfiability of Equality Equations

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 different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

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
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

Example 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

 

Constraints:

  • 1 <= equations.length <= 500
  • equations[i].length == 4
  • equations[i][0] is a lowercase letter.
  • equations[i][1] is either '=' or '!'.
  • equations[i][2] is '='.
  • equations[i][3] is a lowercase letter.

Solution Explanation

This problem can be efficiently solved using the Union-Find algorithm. The core idea is to represent variables as nodes in a graph, and equality equations as edges connecting those nodes. We then process the inequality equations to check for inconsistencies.

Algorithm:

  1. Initialization: Create a parent array p of size 26 (representing lowercase letters 'a' to 'z'). Initialize each element p[i] to i, indicating that each variable initially belongs to its own disjoint set.

  2. Process Equality Equations: Iterate through the input equations. For each equation of the form "x==y":

    • Find the root parent of 'x' (find(x)) and the root parent of 'y' (find(y)).
    • If the roots are different, it means 'x' and 'y' are in different sets. We unite them by setting p[find(x)] = find(y). This ensures that all variables equivalent to 'x' will also be equivalent to 'y'.

  3. Process Inequality Equations: Iterate through the equations again. For each equation of the form "x!=y":

    • Find the root parent of 'x' (find(x)) and the root parent of 'y' (find(y)).
    • If the roots are the same (find(x) == find(y)), it means 'x' and 'y' are in the same set, violating the inequality constraint. Return false.

  4. Return True: If all inequality equations are satisfied, it means a consistent assignment is possible, so return true.

find(x) function: This is a crucial part of Union-Find. It recursively finds the root parent of a node x. Path compression optimization is used to improve efficiency. When a root is found, all nodes along the path to the root are updated to point directly to the root.

Time Complexity Analysis:

  • Initialization: O(1) - Constant time to initialize the parent array.
  • Processing Equality Equations: O(N*α(N)) - where N is the number of equations, and α(N) is the inverse Ackermann function which is practically a constant. The find operation with path compression has amortized time complexity of α(N).
  • Processing Inequality Equations: O(N*α(N)) - Similar to the previous step.
  • Total Time Complexity: O(N*α(N)) which is effectively linear time O(N).

Space Complexity Analysis:

  • O(1) - Constant space because we only use a parent array of fixed size 26.

Example in Python:

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
 
        p = list(range(26))  # Initialize parent array
        for e in equations:
            if e[1] == '=':  # Process equality equations
                a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a')
                p[find(a)] = find(b)
 
        for e in equations:
            if e[1] == '!':  # Process inequality equations
                a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a')
                if find(a) == find(b):
                    return False  # Inconsistent assignment
 
        return True

The code in other languages (Java, C++, Go, Typescript) follows the same algorithm, with minor syntactic variations. They all achieve the same time and space complexity.