We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Satisfiability of Equality Equations

Number: 1032

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Sumo Logic

Problem Description

Given an array of equations in the form "a==b" or "a!=b" where a and b are lowercase letters, determine if it’s possible to assign integers to variables such that all equations hold true.

Key Insights

  • Process all equality equations first to group variables that must be equal.
  • Use the Union Find (Disjoint Set Union) data structure to merge groups.
  • After merging, check each inequality equation; if two variables known to be equal are required to be different, the equations are unsatisfiable.
  • The limited range of variables (typically 26 letters) makes union-find operations efficient.

Space and Time Complexity

Time Complexity: O(n * α(n)) where n is the number of equations and α is the inverse Ackermann function (nearly constant). Space Complexity: O(1) since the number of distinct variables is constant (26).

Solution

We use a Union Find data structure to manage the equivalence between variables. The solution works in two phases:

  1. First pass: Iterate through the equations and perform union operations for every "==" equation, grouping variables that are equal.
  2. Second pass: Iterate through the equations again and for every "!=" equation, check if the two variables belong to the same group. If they do, return false as the equations contradict; otherwise, continue. If no contradiction is found, return true.

The key is processing all equalities first, so that when checking inequalities, the grouping is already established correctly.

Code Solutions

# Python solution using Union Find
class UnionFind:
    def __init__(self):
        # Initialize parent for each lowercase letter ('a'-'z')
        self.parent = {chr(i + ord('a')): chr(i + ord('a')) for i in range(26)}
    
    def find(self, x):
        # Path compression optimization
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Merge the sets that x and y belong to
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY

def equationsPossible(equations):
    uf = UnionFind()
    # First pass: process all "==" equations to union corresponding variables
    for eq in equations:
        if eq[1:3] == "==":
            uf.union(eq[0], eq[3])
    # Second pass: check all "!=" equations
    for eq in equations:
        if eq[1:3] == "!=":
            if uf.find(eq[0]) == uf.find(eq[3]):
                return False
    return True

# Example usage:
equations = ["a==b", "b!=a"]
print(equationsPossible(equations))  # Expected output: False
← Back to All Questions