Introduction

In this blog post, we will explore how to solve the LeetCode problem "990" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 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.

Explanation

Here's the solution:

• Union-Find Data Structure: Use the Union-Find data structure (also known as Disjoint Set Union) to group variables that must be equal. The core idea is that if a == b and b == c, then a, b, and c must belong to the same set/group.

• Equality Constraints: Iterate through the equations, and for each equality constraint (==), union the corresponding variables using the Union-Find's union operation.

• Inequality Constraints: After processing all equality constraints, iterate through the equations again. For each inequality constraint (!=), check if the corresponding variables belong to the same set using the Union-Find's find operation. If they do, it means the inequality cannot be satisfied, so return false. Otherwise, continue. If all inequalities can be satisfied return true.

• Runtime & Storage Complexity: O(n) runtime complexity where n is the number of equations, assuming near-constant time complexity for union-find operations due to path compression and union by rank (or size). O(1) storage complexity, since at most we store 26 parent pointers for the variables from 'a' to 'z'.

Code

    class UnionFind:
    def __init__(self):
        self.parent = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y


def equationsPossible(equations):
    uf = UnionFind()

    # Process equality constraints
    for equation in equations:
        if equation[1] == '=':
            uf.union(equation[0], equation[3])

    # Process inequality constraints
    for equation in equations:
        if equation[1] == '!':
            if uf.find(equation[0]) == uf.find(equation[3]):
                return False

    return True