Satisfiability of Equality Equations

Explanation & Solution

Description

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 forms: "xi==yi" or "xi!=yi". Here, xi and yi are lowercase letters representing 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.

Input:equations = ["a==b","b!=a"]

a==b

b!=a

Output: false

Explanation: If we assign a = 1 and b = 1 to satisfy a==b, then b!=a is not satisfied.

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 either '=' or '!'
equations[i][3] is a lowercase letter

Approach

Union Find pattern

1. Initialize Union Find for 26 Letters

Create a parent array of size 26 (one for each lowercase letter)
Each element is initially its own parent
Track rank for union by rank optimization

2. Process All Equality Equations First

Iterate through equations and process only == equations
For each "x==y", union the indices of x and y
This groups all variables that must be equal into the same component

3. Check All Inequality Equations

Iterate through equations again and process only != equations
For each "x!=y", check if x and y are in the same component
If they are, it's a contradiction — return false

4. Return True if No Contradictions

If all inequality checks pass, the equations are satisfiable
Return true

Key Insight

Process equalities first to build connected components, then verify inequalities don't contradict them
Two-pass approach ensures transitive equalities are captured before checking inequalities

Time

**O(n · α(26))** ≈ **O(n)** where n is the number of equations

Space

O(1)fixed 26-element arrays

Solution Code

Accounts Merge

Most Stones Removed with Same Row or Column