# Solving Leetcode Interviews in Seconds with AI: Satisfiability of Equality Equations


	# 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](https://www.chatmagic.app), 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
	```python
	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
	```