28 · Union-Find & Minimum Spanning Trees

#990 Satisfiability of Equality Equations

frequently reported atAmazon

the problem

In plain words

Each equation is a 4-character string like "a==b" or "a!=b" over lowercase variables. Return true if you can assign integers to the variables so that every equation holds.

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

out false

in ["b==a","a==b"]

out true

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

out false

a, b, c are forced equal, so b != c is impossible.

1 ≤ equations.length ≤ 500
equations[i].length == 4
equations[i][1] is '=' or '!'
equations[i][2] is '='

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternUnion-Find (DSU)

Equality is transitive, so == builds groups. Process all == first (union), then each != just checks its two variables are in different groups.

solutions

From brute force to optimal

Treat == as undirected edges among 26 letters; colour each component; every != must join different colours.

Build adjacency from == equations.
DFS-colour each component with its own id.
Check each !=.

timeO(n)

n equations; the graph has only 26 nodes and ≤ n edges.

spaceO(n)

Adjacency lists hold up to n edges (plus 26 colours).

javajava.util.*

1class Solution {2    public boolean equationsPossible(String[] equations) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < 26; i++) adj.add(new ArrayList<>());5        for (String eq : equations) {6            if (eq.charAt(1) == '=') {7                int a = eq.charAt(0) - 'a', b = eq.charAt(3) - 'a';8                adj.get(a).add(b);9                adj.get(b).add(a);10            }11        }12        int[] color = new int[26];          // component id per letter13        Arrays.fill(color, -1);14        for (int c = 0; c < 26; c++) {15            if (color[c] == -1) paint(adj, c, c, color);16        }17        for (String eq : equations) {18            if (eq.charAt(1) == '!' && color[eq.charAt(0) - 'a'] == color[eq.charAt(3) - 'a']) return false;19        }20        return true;21    }22 23    private void paint(List<List<Integer>> adj, int u, int c, int[] color) {24        color[u] = c;25        for (int v : adj.get(u)) if (color[v] == -1) paint(adj, v, c, color);26    }27}

Pass 1 unions every ==; pass 2 rejects any != whose sides share a root.

parent[26] with parent[i] = i.
For x==y: union(x, y).
For x!=y: if find(x) == find(y) → false.

timeO(n)

Two passes over the equations; with only 26 letters every find is O(1).

spaceO(1)

A fixed array of 26 parents.

javajava.util.*

1class Solution {2    private final int[] parent = new int[26];3 4    private int find(int x) {5        if (parent[x] != x) parent[x] = find(parent[x]);6        return parent[x];7    }8 9    public boolean equationsPossible(String[] equations) {10        for (int i = 0; i < 26; i++) parent[i] = i;11        for (String eq : equations) {               // pass 1: merge every "=="12            if (eq.charAt(1) == '=') parent[find(eq.charAt(0) - 'a')] = find(eq.charAt(3) - 'a');13        }14        for (String eq : equations) {               // pass 2: every "!=" must span two groups15            if (eq.charAt(1) == '!' && find(eq.charAt(0) - 'a') == find(eq.charAt(3) - 'a')) return false;16        }17        return true;18    }19}

in the room

How to say it in the interview

talk track

Point out the order trap: an early != can be broken by a later ==, so all unions must happen before any check.

traps

Checking != while still reading equations in order.
Forgetting a!=a is always false (same root trivially).

what they ask next

Follow-ups

Variables are whole names like "x1", not single letters?

Use a map-based DSU, HashMap<String, String>, as in Accounts Merge. Same two passes; with path compression and union by size each find is near O(1).

Equations carry ratios, like a / b = 2 (Evaluate Division, LC 399)?

Use a weighted DSU: each node stores its ratio to its parent, and find multiplies the ratios along the path. Then a / c is ratio(a) / ratio(c) when they share a root.

before you submit

Edge cases to test

"a!=a" → false on its own.
"z==z" → true (it says nothing).
Only inequalities → always true: give every letter a different number.
An inequality listed before the equalities that break it.

practise next