Course4all

Satisfiability of Equality Equations

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

Satisfiability of Equality Equations

Given equations like 'a==b' or 'b!=a', check if it's possible to satisfy all equations.
Medium

Examples

Input: ["a==b","b!=a"]
Output: false
Approach 1

Level III: Union-Find (Double Pass)

Intuition

Pass 1: Process all '==' and union symbols into components. Pass 2: Process all '!=' and check if the symbols already share a root. If they do, it's a contradiction.
⏱ O(N \cdot \alpha(26))💾 O(26)

Detailed Dry Run

a==b (Union a,b). b==c (Union b,c). a!=c (Find a=c, Find c=c. Conflict!).
java
class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] p = new int[26]; for(int i=0; i<26; i++) p[i]=i;
        for(String e:equations) if(e.charAt(1)=='=') p[find(p, e.charAt(0)-'a')] = find(p, e.charAt(3)-'a');
        for(String e:equations) if(e.charAt(1)=='!' && find(p, e.charAt(0)-'a') == find(p, e.charAt(3)-'a')) return false;
        return true;
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionNumber of Connected Components
Next Question →Most Stones Removed