Satisfiability of Equality Equations

🎯

Satisfiability of Equality Equations

mediumGRAPHAmazonGoogle

Imagine you have a list of statements about equality and inequality between variables, and you want to know if all these statements can be true at the same time.

💡 This problem involves reasoning about relationships between variables. Beginners often struggle because they try to check all pairs naively, missing the power of grouping variables into connected components using union-find.

📋

Problem Statement

Given an array of strings equations that represent relationships between variables, each string is of length 4 and takes one of two forms: 'a==b' or 'a!=b', where a and b are lowercase letters. Determine if it is possible to assign integers to variable names so as to satisfy all the given equations.

1 ≤ equations.length ≤ 10^5equations[i].length == 4equations[i][0] and equations[i][3] are lowercase lettersequations[i][1:3] is either '==' or '!='

💡

Example

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

Output

If a == b and b != a, this is a contradiction, so return false.

Input["b==a","a==b"]

Output

Both equations say a and b are equal, so return true.

Input["a==b","b==c","a==c"]

Output

All variables are equal, no contradictions.

Input["a==b","b!=c","c==a"]

Output

a==b and c==a imply b==c, contradicting b!=c.

• Only equality equations → always true
• Only inequality equations with no conflicts → true
• Variables not connected by any equation → true
• Contradiction arises from indirect equality and inequality → false

⚠️

Common Mistakes

Not separating equality and inequality processing

Incorrectly detecting contradictions too early or missing contradictions

✅ Process all equalities first to union sets, then check inequalities

Not implementing path compression in find()

Union-find operations become slow, leading to TLE

✅ Add path compression to flatten the tree during find

Incorrectly handling union by rank

Union-find tree becomes unbalanced, degrading performance

✅ Use rank to attach smaller tree under larger tree

Checking inequalities before unioning equalities

May falsely detect contradictions

✅ Always process all equalities first

Assuming variables are only 'a' to 'z' without validation

Code may fail or behave unexpectedly with other inputs

✅ Clarify constraints or use a mapping for variables

🧠

Brute Force (Check All Pairs Naively)

💡 This approach exists to build intuition by directly checking all equality and inequality pairs without any optimization. It helps understand the problem's logical requirements before improving efficiency.

Intuition

Try to assign values to variables by checking all equality equations and then verifying if any inequality equation contradicts these assignments.

Algorithm

1. Initialize a mapping from variables to sets of variables they are equal to.
2. For each equality equation, merge the sets of the two variables.
3. For each inequality equation, check if the two variables belong to the same set.
4. If any inequality equation has both variables in the same set, return false; otherwise, return true.

💡 The difficulty is in managing sets of equal variables and checking contradictions without an efficient data structure.

</>

Code

def equationsPossible(equations):
    equal_sets = []
    def find_set(var):
        for s in equal_sets:
            if var in s:
                return s
        return None

    for eq in equations:
        if eq[1:3] == '==':
            set1 = find_set(eq[0])
            set2 = find_set(eq[3])
            if set1 and set2:
                if set1 != set2:
                    set1.update(set2)
                    equal_sets.remove(set2)
            elif set1:
                set1.add(eq[3])
            elif set2:
                set2.add(eq[0])
            else:
                equal_sets.append(set([eq[0], eq[3]]))

    for eq in equations:
        if eq[1:3] == '!=':
            set1 = find_set(eq[0])
            set2 = find_set(eq[3])
            if set1 and set2 and set1 == set2:
                return False
    return True

# Driver code
if __name__ == '__main__':
    test_cases = [
        (['a==b','b!=a'], False),
        (['b==a','a==b'], True),
        (['a==b','b==c','a==c'], True),
        (['a==b','b!=c','c==a'], False)
    ]
    for eqs, expected in test_cases:
        result = equationsPossible(eqs)
        print(f'Input: {eqs} | Output: {result} | Expected: {expected}')

Line Notes

def equationsPossible(equations):Defines the main function to solve the problem

equal_sets = []Stores groups of variables known to be equal

def find_set(var):Helper to find which set a variable belongs to

for eq in equations:Second pass to check inequalities

if eq[1:3] == '==':Identify equality equations

set1 = find_set(eq[0])Find set containing first variable

set2 = find_set(eq[3])Find set containing second variable

if set1 and set2:Both variables already in sets, possibly merge

set1.update(set2)Merge two sets of equal variables

equal_sets.remove(set2)Remove merged set to avoid duplicates

elif set1:Add second variable to existing set

elif set2:Add first variable to existing set

else:Create new set for two variables

if eq[1:3] == '!=':Identify inequality equations

if set1 and set2 and set1 == set2:Contradiction if both variables in same set

return FalseReturn false on contradiction

return TrueReturn true if no contradictions found

import java.util.*;
public class Solution {
    private List<Set<Character>> equalSets = new ArrayList<>();

    private Set<Character> findSet(char var) {
        for (Set<Character> s : equalSets) {
            if (s.contains(var)) return s;
        }
        return null;
    }

    public boolean equationsPossible(String[] equations) {
        for (String eq : equations) {
            if (eq.substring(1, 3).equals("==")) {
                Set<Character> set1 = findSet(eq.charAt(0));
                Set<Character> set2 = findSet(eq.charAt(3));
                if (set1 != null && set2 != null) {
                    if (set1 != set2) {
                        set1.addAll(set2);
                        equalSets.remove(set2);
                    }
                } else if (set1 != null) {
                    set1.add(eq.charAt(3));
                } else if (set2 != null) {
                    set2.add(eq.charAt(0));
                } else {
                    Set<Character> newSet = new HashSet<>();
                    newSet.add(eq.charAt(0));
                    newSet.add(eq.charAt(3));
                    equalSets.add(newSet);
                }
            }
        }

        for (String eq : equations) {
            if (eq.substring(1, 3).equals("!=")) {
                Set<Character> set1 = findSet(eq.charAt(0));
                Set<Character> set2 = findSet(eq.charAt(3));
                if (set1 != null && set2 != null && set1 == set2) {
                    return false;
                }
            }
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[][] tests = {
            {"a==b","b!=a"},
            {"b==a","a==b"},
            {"a==b","b==c","a==c"},
            {"a==b","b!=c","c==a"}
        };
        boolean[] expected = {false, true, true, false};
        for (int i = 0; i < tests.length; i++) {
            boolean res = sol.equationsPossible(tests[i]);
            System.out.println("Input: " + Arrays.toString(tests[i]) + " | Output: " + res + " | Expected: " + expected[i]);
        }
    }
}

Line Notes

private List<Set<Character>> equalSets = new ArrayList<>();Stores sets of equal variables

private Set<Character> findSet(char var) {Helper method to find set containing variable

for (String eq : equations) {Second pass to check inequalities

if (eq.substring(1, 3).equals("==")) {Check for equality equations

Set<Character> set1 = findSet(eq.charAt(0));Find set for first variable

Set<Character> set2 = findSet(eq.charAt(3));Find set for second variable

if (set1 != null && set2 != null) {Both variables in sets, possibly merge

set1.addAll(set2);Merge sets of equal variables

equalSets.remove(set2);Remove merged set to avoid duplicates

else if (set1 != null) {Add second variable to existing set

else if (set2 != null) {Add first variable to existing set

else {Create new set for two variables

if (eq.substring(1, 3).equals("!=")) {Check for inequality equations

if (set1 != null && set2 != null && set1 == set2) {Contradiction if both variables in same set

return false;Return false on contradiction

return true;Return true if no contradictions found

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

set<char>* findSet(char var, vector<set<char>*>& equalSets) {
    for (auto s : equalSets) {
        if (s->count(var)) return s;
    }
    return nullptr;
}

bool equationsPossible(vector<string>& equations) {
    vector<set<char>*> equalSets;
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "==") {
            set<char>* set1 = findSet(eq[0], equalSets);
            set<char>* set2 = findSet(eq[3], equalSets);
            if (set1 && set2) {
                if (set1 != set2) {
                    set1->insert(set2->begin(), set2->end());
                    equalSets.erase(remove(equalSets.begin(), equalSets.end(), set2), equalSets.end());
                    delete set2;
                }
            } else if (set1) {
                set1->insert(eq[3]);
            } else if (set2) {
                set2->insert(eq[0]);
            } else {
                set<char>* newSet = new set<char>({eq[0], eq[3]});
                equalSets.push_back(newSet);
            }
        }
    }
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "!=") {
            set<char>* set1 = findSet(eq[0], equalSets);
            set<char>* set2 = findSet(eq[3], equalSets);
            if (set1 && set2 && set1 == set2) {
                for (auto s : equalSets) delete s;
                return false;
            }
        }
    }
    for (auto s : equalSets) delete s;
    return true;
}

int main() {
    vector<vector<string>> tests = {
        {"a==b","b!=a"},
        {"b==a","a==b"},
        {"a==b","b==c","a==c"},
        {"a==b","b!=c","c==a"}
    };
    vector<bool> expected = {false, true, true, false};
    for (int i = 0; i < tests.size(); i++) {
        bool res = equationsPossible(tests[i]);
        cout << "Input: [";
        for (auto& s : tests[i]) cout << s << ",";
        cout << "] | Output: " << res << " | Expected: " << expected[i] << endl;
    }
    return 0;
}

Line Notes

set<char>* findSet(char var, vector<set<char>*>& equalSets) {Helper to find set containing variable

for (auto& eq : equations) {Second pass to check inequalities

if (eq.substr(1, 2) == "==") {Check for equality equations

set<char>* set1 = findSet(eq[0], equalSets);Find set for first variable

set<char>* set2 = findSet(eq[3], equalSets);Find set for second variable

if (set1 && set2) {Both variables in sets, possibly merge

set1->insert(set2->begin(), set2->end());Merge sets of equal variables

equalSets.erase(remove(equalSets.begin(), equalSets.end(), set2), equalSets.end());Remove merged set

delete set2;Free memory of merged set

else if (set1) {Add second variable to existing set

else if (set2) {Add first variable to existing set

else {Create new set for two variables

if (eq.substr(1, 2) == "!=") {Check for inequality equations

if (set1 && set2 && set1 == set2) {Contradiction if both variables in same set

return false;Return false on contradiction

return true;Return true if no contradictions found

function equationsPossible(equations) {
    let equalSets = [];
    function findSet(v) {
        for (let s of equalSets) {
            if (s.has(v)) return s;
        }
        return null;
    }

    for (let eq of equations) {
        if (eq.slice(1, 3) === '==') {
            let set1 = findSet(eq[0]);
            let set2 = findSet(eq[3]);
            if (set1 && set2) {
                if (set1 !== set2) {
                    for (let val of set2) set1.add(val);
                    equalSets = equalSets.filter(s => s !== set2);
                }
            } else if (set1) {
                set1.add(eq[3]);
            } else if (set2) {
                set2.add(eq[0]);
            } else {
                equalSets.push(new Set([eq[0], eq[3]]));
            }
        }
    }

    for (let eq of equations) {
        if (eq.slice(1, 3) === '!=') {
            let set1 = findSet(eq[0]);
            let set2 = findSet(eq[3]);
            if (set1 && set2 && set1 === set2) return false;
        }
    }
    return true;
}

// Driver code
const tests = [
    [['a==b','b!=a'], false],
    [['b==a','a==b'], true],
    [['a==b','b==c','a==c'], true],
    [['a==b','b!=c','c==a'], false]
];
for (const [eqs, expected] of tests) {
    const res = equationsPossible(eqs);
    console.log(`Input: ${JSON.stringify(eqs)} | Output: ${res} | Expected: ${expected}`);
}

Line Notes

function equationsPossible(equations) {Main function to solve the problem

let equalSets = [];Stores sets of equal variables

function findSet(v) {Helper to find set containing variable

for (let eq of equations) {Second pass to check inequalities

if (eq.slice(1, 3) === '==') {Check for equality equations

let set1 = findSet(eq[0]);Find set for first variable

let set2 = findSet(eq[3]);Find set for second variable

if (set1 && set2) {Both variables in sets, possibly merge

for (let val of set2) set1.add(val);Merge sets of equal variables

equalSets = equalSets.filter(s => s !== set2);Remove merged set

else if (set1) {Add second variable to existing set

else if (set2) {Add first variable to existing set

else {Create new set for two variables

if (eq.slice(1, 3) === '!=') {Check for inequality equations

if (set1 && set2 && set1 === set2) return false;Contradiction if both variables in same set

return true;Return true if no contradictions found

⏱

Complexity

TimeO(n^2) in worst case due to set merging and searching

SpaceO(n) for storing sets of variables

Each equality merges sets which can be costly without efficient data structures; searching sets is linear in number of sets.

💡 For n=1000, this approach might do up to 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Union-Find (Disjoint Set Union) with Two Passes

💡 This approach uses union-find to efficiently group variables connected by equality, then checks inequalities for contradictions. It is a standard and efficient solution.

Intuition

Use union-find to merge variables that must be equal, then verify no inequality equation contradicts these unions.

Algorithm

1. Initialize union-find data structure for all variables.
2. For each equality equation, union the two variables.
3. For each inequality equation, check if the two variables have the same root.
4. If any inequality equation has variables with the same root, return false; otherwise, return true.

💡 The key is to separate processing equalities and inequalities to avoid premature contradictions.

</>

Code

class UnionFind:
    def __init__(self):
        self.parent = {chr(c): chr(c) for c in range(ord('a'), ord('z')+1)}
        self.rank = {chr(c): 0 for c in range(ord('a'), ord('z')+1)}

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1


def equationsPossible(equations):
    uf = UnionFind()
    for eq in equations:
        if eq[1:3] == '==':
            uf.union(eq[0], eq[3])
    for eq in equations:
        if eq[1:3] == '!=':
            if uf.find(eq[0]) == uf.find(eq[3]):
                return False
    return True

# Driver code
if __name__ == '__main__':
    test_cases = [
        (['a==b','b!=a'], False),
        (['b==a','a==b'], True),
        (['a==b','b==c','a==c'], True),
        (['a==b','b!=c','c==a'], False)
    ]
    for eqs, expected in test_cases:
        result = equationsPossible(eqs)
        print(f'Input: {eqs} | Output: {result} | Expected: {expected}')

Line Notes

class UnionFind:Defines union-find data structure

self.parent = {chr(c): chr(c) for c in range(ord('a'), ord('z')+1)}Initialize each variable as its own parent

self.rank = {chr(c): 0 for c in range(ord('a'), ord('z')+1)}Initialize rank for union by rank optimization

def find(self, x):Find root parent with path compression

if self.parent[x] != x:If not root, recursively find root

self.parent[x] = self.find(self.parent[x])Path compression to flatten tree

def union(self, x, y):Union two sets by rank

rootX = self.find(x)Find root of first variable

rootY = self.find(y)Find root of second variable

if rootX != rootY:Only union if roots differ

if self.rank[rootX] < self.rank[rootY]:Attach smaller rank tree under larger

self.parent[rootX] = rootYAttach rootX under rootY

elif self.rank[rootX] > self.rank[rootY]:Attach rootY under rootX

else:If ranks equal, attach and increment rank

uf = UnionFind()Create union-find instance

for eq in equations:Second pass to check inequalities

if eq[1:3] == '==':Process equality equations

uf.union(eq[0], eq[3])Union variables

if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):Contradiction if same root

return FalseReturn false on contradiction

return TrueReturn true if no contradictions

import java.util.*;
public class Solution {
    static class UnionFind {
        private int[] parent = new int[26];
        private int[] rank = new int[26];

        public UnionFind() {
            for (int i = 0; i < 26; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }

    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind();
        for (String eq : equations) {
            if (eq.substring(1, 3).equals("==")) {
                uf.union(eq.charAt(0) - 'a', eq.charAt(3) - 'a');
            }
        }
        for (String eq : equations) {
            if (eq.substring(1, 3).equals("!=")) {
                if (uf.find(eq.charAt(0) - 'a') == uf.find(eq.charAt(3) - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[][] tests = {
            {"a==b","b!=a"},
            {"b==a","a==b"},
            {"a==b","b==c","a==c"},
            {"a==b","b!=c","c==a"}
        };
        boolean[] expected = {false, true, true, false};
        for (int i = 0; i < tests.length; i++) {
            boolean res = sol.equationsPossible(tests[i]);
            System.out.println("Input: " + Arrays.toString(tests[i]) + " | Output: " + res + " | Expected: " + expected[i]);
        }
    }
}

Line Notes

static class UnionFind {Defines union-find data structure

private int[] parent = new int[26];Parent array for 26 lowercase letters

private int[] rank = new int[26];Rank array for union by rank

public UnionFind() {Constructor initializes parent and rank

for (int i = 0; i < 26; i++) {Initialize each variable as its own parent

public int find(int x) {Find root parent with path compression

if (parent[x] != x) {If not root, recursively find root

parent[x] = find(parent[x]);Path compression to flatten tree

public void union(int x, int y) {Union two sets by rank

int rootX = find(x);Find root of first variable

int rootY = find(y);Find root of second variable

if (rootX != rootY) {Only union if roots differ

if (rank[rootX] < rank[rootY]) {Attach smaller rank tree under larger

parent[rootX] = rootY;Attach rootX under rootY

else if (rank[rootX] > rank[rootY]) {Attach rootY under rootX

parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

rank[rootX]++;Increment rank of rootX

UnionFind uf = new UnionFind();Create union-find instance

for (String eq : equations) {Second pass to check inequalities

if (eq.substring(1, 3).equals("==")) {Process equality equations

uf.union(eq.charAt(0) - 'a', eq.charAt(3) - 'a');Union variables

if (eq.substring(1, 3).equals("!=")) {Check inequality equations

if (uf.find(eq.charAt(0) - 'a') == uf.find(eq.charAt(3) - 'a')) {Contradiction if same root

return false;Return false on contradiction

return true;Return true if no contradictions

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

bool equationsPossible(vector<string>& equations) {
    UnionFind uf(26);
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "==") {
            uf.unionSet(eq[0] - 'a', eq[3] - 'a');
        }
    }
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "!=") {
            if (uf.find(eq[0] - 'a') == uf.find(eq[3] - 'a')) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<string>> tests = {
        {"a==b","b!=a"},
        {"b==a","a==b"},
        {"a==b","b==c","a==c"},
        {"a==b","b!=c","c==a"}
    };
    vector<bool> expected = {false, true, true, false};
    for (int i = 0; i < tests.size(); i++) {
        bool res = equationsPossible(tests[i]);
        cout << "Input: [";
        for (auto& s : tests[i]) cout << s << ",";
        cout << "] | Output: " << res << " | Expected: " << expected[i] << endl;
    }
    return 0;
}

Line Notes

class UnionFind {Defines union-find data structure

vector<int> parent, rank;Parent and rank arrays

UnionFind(int n) : parent(n), rank(n, 0) {Constructor initializes arrays

for (int i = 0; i < n; i++) parent[i] = i;Each variable is its own parent initially

int find(int x) {Find root parent with path compression

if (parent[x] != x) {If not root, recursively find root

parent[x] = find(parent[x]);Path compression to flatten tree

void unionSet(int x, int y) {Union two sets by rank

int rootX = find(x);Find root of first variable

int rootY = find(y);Find root of second variable

if (rootX != rootY) {Only union if roots differ

if (rank[rootX] < rank[rootY]) {Attach smaller rank tree under larger

parent[rootX] = rootY;Attach rootX under rootY

else if (rank[rootX] > rank[rootY]) {Attach rootY under rootX

parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

rank[rootX]++;Increment rank of rootX

UnionFind uf(26);Create union-find instance for 26 letters

for (auto& eq : equations) {Second pass to check inequalities

if (eq.substr(1, 2) == "==") {Process equality equations

uf.unionSet(eq[0] - 'a', eq[3] - 'a');Union variables

if (eq.substr(1, 2) == "!=") {Check inequality equations

if (uf.find(eq[0] - 'a') == uf.find(eq[3] - 'a')) {Contradiction if same root

return false;Return false on contradiction

return true;Return true if no contradictions

class UnionFind {
    constructor() {
        this.parent = Array(26).fill(0).map((_, i) => i);
        this.rank = Array(26).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
        }
    }
}

function equationsPossible(equations) {
    const uf = new UnionFind();
    for (const eq of equations) {
        if (eq.slice(1, 3) === '==') {
            uf.union(eq.charCodeAt(0) - 97, eq.charCodeAt(3) - 97);
        }
    }
    for (const eq of equations) {
        if (eq.slice(1, 3) === '!=') {
            if (uf.find(eq.charCodeAt(0) - 97) === uf.find(eq.charCodeAt(3) - 97)) {
                return false;
            }
        }
    }
    return true;
}

// Driver code
const tests = [
    [['a==b','b!=a'], false],
    [['b==a','a==b'], true],
    [['a==b','b==c','a==c'], true],
    [['a==b','b!=c','c==a'], false]
];
for (const [eqs, expected] of tests) {
    const res = equationsPossible(eqs);
    console.log(`Input: ${JSON.stringify(eqs)} | Output: ${res} | Expected: ${expected}`);
}

Line Notes

class UnionFind {Defines union-find data structure

this.parent = Array(26).fill(0).map((_, i) => i);Initialize parent array for 26 letters

this.rank = Array(26).fill(0);Initialize rank array

find(x) {Find root parent with path compression

if (this.parent[x] !== x) {If not root, recursively find root

this.parent[x] = this.find(this.parent[x]);Path compression to flatten tree

union(x, y) {Union two sets by rank

let rootX = this.find(x);Find root of first variable

let rootY = this.find(y);Find root of second variable

if (rootX !== rootY) {Only union if roots differ

if (this.rank[rootX] < this.rank[rootY]) {Attach smaller rank tree under larger

this.parent[rootX] = rootY;Attach rootX under rootY

else if (this.rank[rootX] > this.rank[rootY]) {Attach rootY under rootX

this.parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

this.rank[rootX]++;Increment rank of rootX

const uf = new UnionFind();Create union-find instance

for (const eq of equations) {Second pass to check inequalities

if (eq.slice(1, 3) === '==') {Process equality equations

uf.union(eq.charCodeAt(0) - 97, eq.charCodeAt(3) - 97);Union variables

if (eq.slice(1, 3) === '!=') {Check inequality equations

if (uf.find(eq.charCodeAt(0) - 97) === uf.find(eq.charCodeAt(3) - 97)) {Contradiction if same root

return false;Return false on contradiction

return true;Return true if no contradictions

⏱

Complexity

TimeO(n α(n)) where α is inverse Ackermann function, practically constant

SpaceO(1) since only 26 variables are tracked

Union-find operations are almost constant time; two passes over equations yield linear time.

💡 For n=10^5, this approach runs efficiently within milliseconds.

Interview Verdict: Accepted / Optimal for this problem

This is the standard and efficient solution expected in interviews.

🧠

Union-Find with Early Contradiction Detection

💡 This approach improves on the previous by checking inequalities during union operations to detect contradictions earlier, potentially saving time.

Intuition

While unioning equal variables, if an inequality contradicts the union, return false immediately.

Algorithm

1. Initialize union-find for all variables.
2. Process all equality equations, unioning variables.
3. While processing inequalities, if variables are already connected, return false immediately.
4. If no contradictions found, return true.

💡 Failing fast on contradictions can save time on large inputs.

</>

Code

class UnionFind:
    def __init__(self):
        self.parent = {chr(c): chr(c) for c in range(ord('a'), ord('z')+1)}
        self.rank = {chr(c): 0 for c in range(ord('a'), ord('z')+1)}

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1


def equationsPossible(equations):
    uf = UnionFind()
    for eq in equations:
        if eq[1:3] == '==':
            uf.union(eq[0], eq[3])
    for eq in equations:
        if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):
            return False
    return True

# Driver code
if __name__ == '__main__':
    test_cases = [
        (['a==b','b!=a'], False),
        (['b==a','a==b'], True),
        (['a==b','b==c','a==c'], True),
        (['a==b','b!=c','c==a'], False)
    ]
    for eqs, expected in test_cases:
        result = equationsPossible(eqs)
        print(f'Input: {eqs} | Output: {result} | Expected: {expected}')

Line Notes

class UnionFind:Defines union-find data structure

self.parent = {chr(c): chr(c) for c in range(ord('a'), ord('z')+1)}Initialize each variable as its own parent

self.rank = {chr(c): 0 for c in range(ord('a'), ord('z')+1)}Initialize rank for union by rank optimization

def find(self, x):Find root parent with path compression

if self.parent[x] != x:If not root, recursively find root

self.parent[x] = self.find(self.parent[x])Path compression to flatten tree

def union(self, x, y):Union two sets by rank

rootX = self.find(x)Find root of first variable

rootY = self.find(y)Find root of second variable

if rootX != rootY:Only union if roots differ

if self.rank[rootX] < self.rank[rootY]:Attach smaller rank tree under larger

self.parent[rootX] = rootYAttach rootX under rootY

elif self.rank[rootX] > self.rank[rootY]:Attach rootY under rootX

self.parent[rootY] = rootXAttach rootY under rootX

else:If ranks equal, attach and increment rank

self.rank[rootX] += 1Increment rank of rootX

uf = UnionFind()Create union-find instance

for eq in equations:Second pass to check inequalities

if eq[1:3] == '==':Process equality equations

uf.union(eq[0], eq[3])Union variables

if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):Fail fast if contradiction found

return FalseReturn false on contradiction

return TrueReturn true if no contradictions

import java.util.*;
public class Solution {
    static class UnionFind {
        private int[] parent = new int[26];
        private int[] rank = new int[26];

        public UnionFind() {
            for (int i = 0; i < 26; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }

    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind();
        for (String eq : equations) {
            if (eq.substring(1, 3).equals("==")) {
                uf.union(eq.charAt(0) - 'a', eq.charAt(3) - 'a');
            }
        }
        for (String eq : equations) {
            if (eq.substring(1, 3).equals("!=") && uf.find(eq.charAt(0) - 'a') == uf.find(eq.charAt(3) - 'a')) {
                return false;
            }
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[][] tests = {
            {"a==b","b!=a"},
            {"b==a","a==b"},
            {"a==b","b==c","a==c"},
            {"a==b","b!=c","c==a"}
        };
        boolean[] expected = {false, true, true, false};
        for (int i = 0; i < tests.length; i++) {
            boolean res = sol.equationsPossible(tests[i]);
            System.out.println("Input: " + Arrays.toString(tests[i]) + " | Output: " + res + " | Expected: " + expected[i]);
        }
    }
}

Line Notes

static class UnionFind {Defines union-find data structure

private int[] parent = new int[26];Parent array for 26 lowercase letters

private int[] rank = new int[26];Rank array for union by rank

public UnionFind() {Constructor initializes parent and rank

for (int i = 0; i < 26; i++) {Initialize each variable as its own parent

public int find(int x) {Find root parent with path compression

if (parent[x] != x) {If not root, recursively find root

parent[x] = find(parent[x]);Path compression to flatten tree

public void union(int x, int y) {Union two sets by rank

int rootX = find(x);Find root of first variable

int rootY = find(y);Find root of second variable

if (rootX != rootY) {Only union if roots differ

if (rank[rootX] < rank[rootY]) {Attach smaller rank tree under larger

parent[rootX] = rootY;Attach rootX under rootY

else if (rank[rootX] > rank[rootY]) {Attach rootY under rootX

parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

rank[rootX]++;Increment rank of rootX

UnionFind uf = new UnionFind();Create union-find instance

for (String eq : equations) {Second pass to check inequalities

if (eq.substring(1, 3).equals("==")) {Process equality equations

uf.union(eq.charAt(0) - 'a', eq.charAt(3) - 'a');Union variables

if (eq.substring(1, 3).equals("!=") && uf.find(eq.charAt(0) - 'a') == uf.find(eq.charAt(3) - 'a')) {Fail fast if contradiction found

return false;Return false on contradiction

return true;Return true if no contradictions

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

bool equationsPossible(vector<string>& equations) {
    UnionFind uf(26);
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "==") {
            uf.unionSet(eq[0] - 'a', eq[3] - 'a');
        }
    }
    for (auto& eq : equations) {
        if (eq.substr(1, 2) == "!=") {
            if (uf.find(eq[0] - 'a') == uf.find(eq[3] - 'a')) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<string>> tests = {
        {"a==b","b!=a"},
        {"b==a","a==b"},
        {"a==b","b==c","a==c"},
        {"a==b","b!=c","c==a"}
    };
    vector<bool> expected = {false, true, true, false};
    for (int i = 0; i < tests.size(); i++) {
        bool res = equationsPossible(tests[i]);
        cout << "Input: [";
        for (auto& s : tests[i]) cout << s << ",";
        cout << "] | Output: " << res << " | Expected: " << expected[i] << endl;
    }
    return 0;
}

Line Notes

class UnionFind {Defines union-find data structure

vector<int> parent, rank;Parent and rank arrays

UnionFind(int n) : parent(n), rank(n, 0) {Constructor initializes arrays

for (int i = 0; i < n; i++) parent[i] = i;Each variable is its own parent initially

int find(int x) {Find root parent with path compression

if (parent[x] != x) {If not root, recursively find root

parent[x] = find(parent[x]);Path compression to flatten tree

void unionSet(int x, int y) {Union two sets by rank

int rootX = find(x);Find root of first variable

int rootY = find(y);Find root of second variable

if (rootX != rootY) {Only union if roots differ

if (rank[rootX] < rank[rootY]) {Attach smaller rank tree under larger

parent[rootX] = rootY;Attach rootX under rootY

else if (rank[rootX] > rank[rootY]) {Attach rootY under rootX

parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

rank[rootX]++;Increment rank of rootX

UnionFind uf(26);Create union-find instance for 26 letters

for (auto& eq : equations) {Second pass to check inequalities

if (eq.substr(1, 2) == "==") {Process equality equations

uf.unionSet(eq[0] - 'a', eq[3] - 'a');Union variables

if (eq.substr(1, 2) == "!=") {Check inequality equations

if (uf.find(eq[0] - 'a') == uf.find(eq[3] - 'a')) {Fail fast if contradiction found

return false;Return false on contradiction

return true;Return true if no contradictions

class UnionFind {
    constructor() {
        this.parent = Array(26).fill(0).map((_, i) => i);
        this.rank = Array(26).fill(0);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
        }
    }
}

function equationsPossible(equations) {
    const uf = new UnionFind();
    for (const eq of equations) {
        if (eq.slice(1, 3) === '==') {
            uf.union(eq.charCodeAt(0) - 97, eq.charCodeAt(3) - 97);
        }
    }
    for (const eq of equations) {
        if (eq.slice(1, 3) === '!=') {
            if (uf.find(eq.charCodeAt(0) - 97) === uf.find(eq.charCodeAt(3) - 97)) {
                return false;
            }
        }
    }
    return true;
}

// Driver code
const tests = [
    [['a==b','b!=a'], false],
    [['b==a','a==b'], true],
    [['a==b','b==c','a==c'], true],
    [['a==b','b!=c','c==a'], false]
];
for (const [eqs, expected] of tests) {
    const res = equationsPossible(eqs);
    console.log(`Input: ${JSON.stringify(eqs)} | Output: ${res} | Expected: ${expected}`);
}

Line Notes

class UnionFind {Defines union-find data structure

this.parent = Array(26).fill(0).map((_, i) => i);Initialize parent array for 26 letters

this.rank = Array(26).fill(0);Initialize rank array

find(x) {Find root parent with path compression

if (this.parent[x] !== x) {If not root, recursively find root

this.parent[x] = this.find(this.parent[x]);Path compression to flatten tree

union(x, y) {Union two sets by rank

let rootX = this.find(x);Find root of first variable

let rootY = this.find(y);Find root of second variable

if (rootX !== rootY) {Only union if roots differ

if (this.rank[rootX] < this.rank[rootY]) {Attach smaller rank tree under larger

this.parent[rootX] = rootY;Attach rootX under rootY

else if (this.rank[rootX] > this.rank[rootY]) {Attach rootY under rootX

this.parent[rootY] = rootX;Attach rootY under rootX

else {If ranks equal, attach and increment rank

this.rank[rootX]++;Increment rank of rootX

const uf = new UnionFind();Create union-find instance

for (const eq of equations) {Second pass to check inequalities

if (eq.slice(1, 3) === '==') {Process equality equations

uf.union(eq.charCodeAt(0) - 97, eq.charCodeAt(3) - 97);Union variables

if (eq.slice(1, 3) === '!=') {Check inequality equations

if (uf.find(eq.charCodeAt(0) - 97) === uf.find(eq.charCodeAt(3) - 97)) {Fail fast if contradiction found

return false;Return false on contradiction

return true;Return true if no contradictions

⏱

Complexity

TimeO(n α(n)) similar to previous approach

SpaceO(1) for fixed 26 variables

Early contradiction detection does not change asymptotic complexity but can improve runtime in practice.

💡 This approach is a practical optimization to detect conflicts sooner.

Interview Verdict: Accepted / Slightly optimized

This approach is recommended for interviews to show awareness of optimization.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the union-find approach with two passes in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Union-Find with Two Passes	O(n α(n))	O(1)	No	N/A	Code this approach
3. Union-Find with Early Contradiction Detection	O(n α(n))	O(1)	No	N/A	Optional optimization to mention

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the union-find solution, and prepare to explain your approach clearly in interviews.

How to Present

Step 1: Clarify input format and constraints.Step 2: Describe brute force approach and its inefficiency.Step 3: Introduce union-find data structure and how it groups equal variables.Step 4: Explain two-pass approach: union equalities, then check inequalities.Step 5: Code the union-find solution with path compression and union by rank.Step 6: Test with examples and edge cases.Step 7: Discuss possible optimizations and tradeoffs.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of union-find, ability to implement it correctly, and reasoning about equality and inequality constraints.

Common Follow-ups

• What if variables are not limited to lowercase letters? → Use a map from variable to id.
• Can you solve this with graph coloring? → Yes, but union-find is more efficient here.

💡 Follow-ups test your ability to generalize and consider alternative approaches.

🔍

Pattern Recognition

When to Use

1) Problem involves variables with equality and inequality constraints; 2) Need to check if all constraints can be satisfied simultaneously; 3) Variables can be grouped by equality; 4) Efficient union/find or graph connectivity is applicable.

Signature Phrases

'a==b''a!=b''satisfiability of equations'

NOT This Pattern When

Problems that require shortest path or max flow are different despite involving graphs.

Similar Problems

Equations Possible - same problem on LeetCodeGraph Connectivity - grouping nodes by connectivityChecking Consistency in Constraints - general constraint satisfaction

Practice

1. Consider the following Python code implementing the optimal solution for the problem. Given the input n = 4 and edges = [[3,1,2],[3,2,3],[1,1,3],[2,3,4]], what is the final return value of max_num_edges_to_remove_sorted(n, edges)?

easy

A. 3

B. 2

C. 1

D. -1

Solution

1. Step 1: Sort edges by type descending

   Edges sorted: type 3 edges first: [3,1,2], [3,2,3], then type 1: [1,1,3], then type 2: [2,3,4].

2. Step 2: Process edges with union-find

   Type 3 edges connect nodes 0-1 and 1-2 for both Alice and Bob, used=2. Type 1 edge connects 0-2 for Alice, but already connected, so no increment. Type 2 edge connects 2-3 for Bob, used=3 total. Both have count=1 (fully connected). Edges used=3, total edges=4, so removable=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Used edges=3, removable=4-3=1 -> careful: used=3, removable=1 [OK]

Hint: Count used edges after union-find merges [OK]

Common Mistakes:

• Off-by-one in indexing nodes
• Ignoring type 3 edges first
• Counting used edges incorrectly

2. What is the time complexity of Kruskal's algorithm using union-find with path compression and union by size on a graph with n vertices and m edges?

medium

A. O(m log m + m α(n))

B. O(n^2)

C. O(m n)

D. O(m log n)

Solution

1. Step 1: Identify sorting cost

   Sorting edges takes O(m log m) time, which is equivalent to O(m log n) since m ≤ n^2.

2. Step 2: Analyze union-find operations

   Union-find operations take O(m α(n)) where α(n) is inverse Ackermann function, almost constant.

3. Step 3: Combine complexities

   The total complexity is O(m log n) dominated by sorting, as α(n) is negligible.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Sorting dominates, union-find nearly linear [OK]

Hint: Sorting edges + near-linear union-find cost dominates [OK]

Common Mistakes:

• Confusing α(n) with log n or n
• Assuming union-find is O(n) per operation
• Ignoring sorting cost or assuming O(m log n)

3. Examine the following buggy Union-Find code snippet for the network connectivity problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with 'return self.find(self.parent[x])' in find method

B. Line 'self.count = n' in __init__ method

C. Line 'self.rank[rootX] += 1' in union method

D. Line 'self.parent[rootX] = rootY' in union method

Solution

1. Step 1: Identify path compression implementation

   The find method should assign the parent during recursion: self.parent[x] = self.find(self.parent[x]) to flatten the tree.

2. Step 2: Understand impact of missing assignment

   Without path compression, find operations become slower and can cause TLE or incorrect component counts on large inputs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing path compression assignment is a classic subtle bug [OK]

Hint: Path compression requires assignment to parent during find [OK]

Common Mistakes:

• Forgetting path compression assignment
• Misplacing rank increment
• Incorrectly decrementing count

4. What is the time complexity of the optimal union-find + priority queue approach to the smallest string with swaps problem, where n is the length of the string and m is the number of pairs?

medium

A. O(n log n + m α(n)) where α(n) is the inverse Ackermann function from union-find operations

B. O(n * m) due to iterating over all pairs for each character

C. O(n²) because sorting characters in each connected component can be quadratic in worst case

D. O(m log n) because union-find operations dominate the runtime

Solution

1. Step 1: Analyze union-find operations

   Union-find performs m union/find operations in O(m α(n)) time, where α(n) is very slow growing and almost constant.

2. Step 2: Analyze sorting step

   Sorting characters in all connected components combined takes O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find plus sorting dominates runtime as O(n log n + m α(n)) [OK]

Hint: Union-find nearly linear; sorting dominates with n log n [OK]

Common Mistakes:

• Assuming O(n*m) due to nested loops
• Confusing sorting cost as O(n²)
• Ignoring inverse Ackermann factor

5. Suppose the Accounts Merge problem is extended so that emails can be reused across multiple users (e.g., shared family emails). Which modification to the union-find approach correctly handles this scenario?

hard

A. Use a graph with edges between accounts and emails, then find connected components allowing multiple parents

B. Keep union-find as is; emails connected once belong to a single user

C. Modify union-find to allow multiple parents per node to represent shared emails

D. Assign emails to users greedily by first occurrence, ignoring overlaps

Solution

1. Step 1: Understand the new constraint

   Emails can belong to multiple users, so union-find's single parent per node model breaks down.

2. Step 2: Choose correct data structure

   A bipartite graph connecting accounts and emails with connected components allows shared emails without forcing merges.

3. Step 3: Evaluate other options

   Union-find cannot represent multiple parents; greedy assignment loses correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Graph approach models shared emails correctly [OK]

Hint: Union-find assumes disjoint sets; shared emails break this [OK]

Common Mistakes:

• Trying to modify union-find for multiple parents
• Ignoring shared emails and merging incorrectly