Satisfiability Of Equality Equations - Leetcode Solution

Problem statement:

Given an array of strings equations, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-digit integers.

Return true if and only if it is possible to assign digits to letters so that the equalities and inequalities stated in equations are satisfied.

Example 1:

Input: ["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: ["b==a","a==b"] Output: true Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

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

Example 4:

Input: ["a==b","b!=c","c==a"] Output: false Explanation: If we assign a = 1, b = 2, and c = 1, then the first and third equations are satisfied but not the second. There is no way to assign the variables to satisfy all the equations.

Solution:

We can solve this problem using the union-find algorithm. The basic idea is to first create separate groups of all the equality equations using union-find and then check for any inequality equations that violate these groups. If we can't find any such inequality equations, then all the equations can be satisfied.

For implementing union-find, we can use an array representing the parent node of each element. Initially, all elements are their own parent nodes. To find the parent node of an element, we can traverse the parent nodes until we find an element whose parent node is itself. This is the root node of the group.

We can now create separate groups for all the elements that are part of an equality equation by calling union on their parent nodes. This will make all these elements part of the same group, and their root node will be the same.

After creating separate groups for all the equality equations, we can check for any inequality equation that violates these groups. For this, we can check if the parent nodes of the two elements in the inequality equation are the same. If they are the same, then it means that they are part of the same group, which violates the inequality equation. In this case, we can return false, indicating that the equations cannot be satisfied.

If we don't find any such inequality equations that violate the groups, then all the equations can be satisfied, and we can return true.

Code:

Here is the python code implementing the above algorithm:

class UnionFind: def init(self): self.parent = [i for i in range(26)] # Initially, all nodes are their own parent

def find(self, x):
    if self.parent[x] == x:
        return x

    # Path compression
    self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

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

class Solution: def equationsPossible(self, equations: List[str]) -> bool: uf = UnionFind()

    # Creating separate groups for all the equality equations
    for eq in equations:
        if eq[1] == '=':
            uf.union(ord(eq[0])-ord('a'), ord(eq[3])-ord('a'))

    # Checking for any inequality equations that violate the groups
    for eq in equations:
        if eq[1] == '!':
            if uf.find(ord(eq[0])-ord('a')) == uf.find(ord(eq[3])-ord('a')):
                return False

    return True

Time complexity: O(nlogn) Space complexity: O(n)

The time complexity of the algorithm is dominated by the union-find operations, which take O(logn) time on average. Since we are calling union-find n times, the overall time complexity of the algorithm is O(nlogn). The space complexity is O(n) for storing the parent array.

1