Problem 25.2 · Union-Find (DSU)Medium

Satisfiability of Equality Equations

What it teaches: Equivalence classes: union all equalities first, then check every inequality.

Practise it on judges as “Satisfiability of Equality Equations”.

The problem

Each equation is "a==b" or "a!=b" with single lowercase letters. Return true if some assignment of numbers to letters satisfies all equations.

Example 1

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

Example 2

Input: ["a==b", "b==c", "a==c"]
Output: true

Constraints

1 ≤ equations ≤ 500

Pattern clues in the wording

→ == is transitive
→ Check != against groups

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean equationsPossible(String[] equations) {
        return true;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	equations = ["a==b","b!=a"]	false
2	equations = ["b==a","a==b"]	true
3	equations = ["a==b","b!=c","c==a"]	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Two-pass union-find over 26 letters · O(n α(26))

Two-pass union-find over 26 letters

Time O(n α(26)) Space O(26)

Union both sides of every ==. Then for every !=, if both sides share a root, return false.

Approach 1

class Solution {
    private final int[] parent = new int[26];

    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < 26; i++) parent[i] = i;
        for (String e : equations)
            if (e.charAt(1) == '=') parent[find(e.charAt(0) - 'a')] = find(e.charAt(3) - 'a');
        for (String e : equations)
            if (e.charAt(1) == '!' && find(e.charAt(0) - 'a') == find(e.charAt(3) - 'a')) return false;
        return true;
    }

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

Verdict: Order of passes matters; equalities must be complete first.

Before you submit

Edge cases and common mistakes

Test these inputs

"a!=a" (always false)
Only inequalities

Mistakes people make

Checking inequalities while still adding equalities (a later == can break them).

Interview

Follow-up questions

What if the relation were < instead of !=?

Command Palette

The problem

Approaches

Two-pass union-find over 26 letters

Edge cases and common mistakes

Follow-up questions