200. Satisfiability of Equality Equations
๐ LeetCode Problem: 990. Satisfiability of Equality Equations
๐ Difficulty: Medium
๐ท๏ธ Topics: Graph, Union-Find, Array, String
Problem Statement
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 different forms: "xแตข==yแตข" or "xแตข!=yแตข". Here, xแตข and yแตข are lowercase letters (not necessarily different) that represent one-letter 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.
Example 1:
Input: equations = ["a==b","b!=a"]
Output: false
Explanation:
If we assign a = 1 and b = 1, then a==b is satisfied.
But then b!=a requires b โ a, which is impossible!
Contradiction! Return false.
Example 2:
Input: equations = ["b==a","a==b"]
Output: true
Explanation:
We can assign a = 1 and b = 1.
Both equations satisfied!
No contradiction. Return true.
Example 3:
Input: equations = ["a==b","b==c","a==c"]
Output: true
Explanation:
Transitive equality: if a==b and b==c, then a==c.
We can assign a = b = c = 1.
All satisfied!
Example 4:
Input: equations = ["a==b","b!=c","c==a"]
Output: false
Explanation:
a==b means a and b are equal.
c==a means c and a are equal.
โ Transitive: c == b
But b!=c says they're NOT equal!
Contradiction! Return false.
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 '='.
- equations[i][3] is a lowercase letter.
๐ณ Visual Understanding - The Complete Picture
The Problem We're Solving ๐ค
Given equations with == and !=, check if all can be satisfied: โ๏ธ
Two types of equations:
a==b: variables a and b MUST be equal โ
a!=b: variables a and b MUST be different โ
Question: Can we assign values to satisfy ALL equations?
Example 1: POSSIBLE โ
equations = ["a==b", "b==c"]
Assign: a = 1, b = 1, c = 1
Check: a==b? 1==1 โ
b==c? 1==1 โ
All satisfied! Return true โ
Example 2: IMPOSSIBLE โ
equations = ["a==b", "b!=a"]
a==b requires: a = b
b!=a requires: b โ a
Contradiction! Can't satisfy both!
Return false โ
Understanding Transitivity ๐
Key insight: Equality is TRANSITIVE!
If a==b and b==c, then automatically a==c! ๐ฏ
Example:
equations = ["a==b", "b==c", "c!=a"]
From a==b and b==c:
โ a, b, c must all be equal (transitive!)
But c!=a says c โ a!
Contradiction! โ
This is where Union-Find shines! ๐ก
Why Union-Find is Perfect! ๐ฏ
Union-Find naturally handles equality groups! ๐
Strategy:
1. Process all == equations first
โ Union variables that must be equal
โ Forms groups of equal variables
2. Check all != equations
โ If two variables in != are in same group...
โ They're equal (contradiction!) โ
โ Otherwise, they can be different โ
Example:
equations = ["a==b", "b==c", "a!=d"]
Step 1: Process ==
a==b: union(a, b) โ {a, b}
b==c: union(b, c) โ {a, b, c}
Step 2: Check !=
a!=d: find(a) == find(d)?
NO! Different groups โ
They can be different!
Return true! โ
Union-Find groups equal variables! ๐ก
๐ง The Journey - Building Intuition
Part 1: Understanding Constraints - "What's allowed?" ๐ค
๐ญ Think of it like algebraic equations:
Equation a==b means:
"Variable a and b have SAME value"
If a = 5, then b = 5
Equation a!=b means:
"Variable a and b have DIFFERENT values"
If a = 5, then b โ 5 (could be 1, 2, 3, 4, 6, ...)
Can we assign values to satisfy ALL equations?
Example 1: YES โ
a==b, b==c
Set: a = 1, b = 1, c = 1
Works! All equations true!
Example 2: NO โ
a==b, b!=a
a==b requires a = b
b!=a requires b โ a
Impossible! Contradiction!
Part 2: The Key Insight - "Groups of Equal Variables" ๐ฅ
๐ญ Equality creates GROUPS!
If a==b and b==c:
Then a, b, c are all in same "equality group"
They must ALL have the same value!
Visual:
Initial: {a}, {b}, {c}, {d}
After a==b: {a, b}, {c}, {d}
After b==c: {a, b, c}, {d}
Now we know:
a, b, c must all be equal (same group)
d can be anything (different group)
This is EXACTLY what Union-Find does! ๐ฏ
Part 3: Two-Phase Strategy ๐
๐ญ Smart approach: Process in TWO phases!
PHASE 1: Build equality groups (process ==)
For each equation x==y:
Union x and y
They're in same group now!
Result: Groups of variables that must be equal
PHASE 2: Check inequalities (validate !=)
For each equation x!=y:
Check: Are x and y in same group?
If YES โ They must be equal (from phase 1)
But != says they must be different!
CONTRADICTION! โ Return false
If NO โ Different groups, can be different โ
Continue checking
If all != equations pass โ Return true! โ
Part 4: Example Walkthrough ๐
๐ญ Let's trace a complex example:
equations = ["a==b", "b==c", "c!=d", "d==e", "e!=a"]
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ PHASE 1: Process == equations (build groups) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Initial groups: {a}, {b}, {c}, {d}, {e}
Process "a==b":
union(a, b)
Groups: {a, b}, {c}, {d}, {e}
Process "b==c":
union(b, c)
Groups: {a, b, c}, {d}, {e}
Process "d==e":
union(d, e)
Groups: {a, b, c}, {d, e}
After phase 1:
Group 1: {a, b, c} - all must be equal
Group 2: {d, e} - all must be equal
Group 1 and 2 can have different values! โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ PHASE 2: Check != equations (validate) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Check "c!=d":
find(c) = leader of {a,b,c}
find(d) = leader of {d,e}
Same group? NO! โ
They can be different! Continue...
Check "e!=a":
find(e) = leader of {d,e}
find(a) = leader of {a,b,c}
Same group? NO! โ
They can be different! Continue...
All != equations satisfied! โ
Return true!
Assignment example:
a = b = c = 1
d = e = 2
All equations satisfied! ๐
Part 5: Why Two Phases? ๐ก
๐ญ Why not just process in order?
Because transitivity needs to be established first!
Example: ["c!=a", "a==b", "b==c"]
If we process in order:
"c!=a": Check find(c) == find(a)?
They're separate... looks OK? โ
"a==b": union(a, b)
"b==c": union(b, c)
Now a, b, c all in same group!
But we already validated c!=a! โ
We missed the contradiction!
Correct approach (two phases):
Phase 1: Process ALL ==
a==b: union(a, b) โ {a, b}
b==c: union(b, c) โ {a, b, c}
Now we know: a, b, c must all be equal
Phase 2: Check ALL !=
c!=a: find(c) == find(a)?
YES! Same group! โ
CONTRADICTION!
Return false! โ
Two phases ensures we catch all contradictions! ๐ฏ
Part 6: The Algorithm - Clean and Simple! โจ
โจ Complete algorithm:
PHASE 1: Build equality groups
Initialize Union-Find for 26 letters
For each equation:
If equation is "x==y":
union(x, y)
PHASE 2: Validate inequalities
For each equation:
If equation is "x!=y":
If find(x) == find(y):
return false // Contradiction! โ
return true // All constraints satisfied! โ
Time: O(n ร ฮฑ(n)) where n = number of equations
Space: O(1) - only 26 letters!
Elegant and efficient! ๐
๐ฏ Approach: Union-Find (Optimal!)
The Key Insight ๐ก
Use Union-Find to group equal variables ๐! Two-phase strategy: First, process all == equations to build equality groups using union ๐ค. Then, check all != equations to validate no contradictions ๐. If variables in != are in same group โ contradiction! โ Otherwise satisfiable! โ
Time: O(n ร ฮฑ(n)) โก, Space: O(1) - only 26 letters! ๐ฆ
Perfect for constraint satisfaction! ๐
Complete Implementation
class Solution {
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// UNION-FIND FOR CONSTRAINT SATISFACTION ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
private int[] parent;
private int[] rank;
public boolean equationsPossible(String[] equations) {
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// TWO-PHASE APPROACH ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Phase 1: Process == (build equality groups)
// Phase 2: Check != (validate no contradictions)
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// INITIALIZE UNION-FIND FOR 26 LETTERS ๐๏ธ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
parent = new int[26]; // a-z mapped to 0-25
rank = new int[26];
for (int i = 0; i < 26; i++) {
parent[i] = i; // Each letter is its own parent
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// PHASE 1: PROCESS == EQUATIONS ๐ค
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Build groups of variables that must be equal
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
for (String eq : equations) {
if (eq.charAt(1) == '=') { // This is "x==y"
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// EXTRACT VARIABLES
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
char x = eq.charAt(0);
char y = eq.charAt(3);
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// UNION THEM - they must be equal! ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
union(x - 'a', y - 'a');
}
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// PHASE 2: CHECK != EQUATIONS ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Validate that no != equation is violated
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
for (String eq : equations) {
if (eq.charAt(1) == '!') { // This is "x!=y"
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// EXTRACT VARIABLES
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
char x = eq.charAt(0);
char y = eq.charAt(3);
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// CHECK: Are they in same group? ๐ฏ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
if (find(x - 'a') == find(y - 'a')) {
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// SAME GROUP! โ
// They must be equal (from phase 1)
// But != says they must be different!
// CONTRADICTION!
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
return false;
}
}
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// ALL CONSTRAINTS SATISFIED! โ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
return true;
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// FIND: Get leader with path compression โก
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
private int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression!
}
return parent[x];
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// UNION: Merge two groups by rank ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
private void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return; // Already in same group
// Union by rank
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
Why This Works ๐ฏ
Two-phase strategy catches all contradictions: ๐ - Phase 1 establishes ALL equality relationships - Transitive equalities automatically handled by Union-Find - Phase 2 checks against complete equality groups!
Union-Find groups equal variables: ๐ - Variables in same group must have same value - Variables in different groups can be different - Perfect for constraint checking!
Space-efficient: ๐ฆ - Only 26 letters possible (a-z) - O(1) space regardless of input size!
๐ Detailed Dry Run
Let's trace on:
equations = ["a==b","b==c","c!=d","a!=d"]
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ INITIALIZATION โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
26 letters (a-z) mapped to indices 0-25:
a=0, b=1, c=2, d=3, ...
Initialize Union-Find:
parent = [0, 1, 2, 3, 4, ..., 25]
rank = [0, 0, 0, 0, 0, ..., 0]
Initial groups: {a}, {b}, {c}, {d}, ...
(Each letter is its own group)
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ PHASE 1: PROCESS == EQUATIONS โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 1: "a==b" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Extract: x = 'a' (index 0) โ
โ y = 'b' (index 1) โ
โ โ
โ union(0, 1): โ
โ rootX = find(0) = 0 โ
โ rootY = find(1) = 1 โ
โ rank[0] == rank[1] (both 0) โ
โ parent[1] = 0 โ
โ rank[0]++ โ 1 โ
โ โ
โ Result: โ
โ parent = [0, 0, 2, 3, 4, ..., 25] โ
โ rank = [1, 0, 0, 0, 0, ..., 0] โ
โ โ
โ Groups: {a, b}, {c}, {d}, ... โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 2: "b==c" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Extract: x = 'b' (index 1) โ
โ y = 'c' (index 2) โ
โ โ
โ union(1, 2): โ
โ rootX = find(1) = 0 (b's root is a) โ
โ rootY = find(2) = 2 โ
โ rank[0] = 1, rank[2] = 0 โ
โ rank[0] > rank[2] โ
โ parent[2] = 0 โ
โ โ
โ Result: โ
โ parent = [0, 0, 0, 3, 4, ..., 25] โ
โ โ
โ Visual: โ
โ 0 (a) โ
โ / \ โ
โ 1 2 โ
โ (b) (c) โ
โ โ
โ Groups: {a, b, c}, {d}, ... โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 3: "c!=d" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ This is != equation โ
โ SKIP in Phase 1 (only process == here) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 4: "a!=d" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ This is != equation โ
โ SKIP in Phase 1 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
After Phase 1:
Groups: {a, b, c}, {d}, {e}, ...
Meaning: a, b, c must all be equal
d can be anything different
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ PHASE 2: CHECK != EQUATIONS โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 1: "a==b" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ This is == equation โ
โ SKIP in Phase 2 (only check != here) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 2: "b==c" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ SKIP (== equation) โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 3: "c!=d" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Extract: x = 'c' (index 2) โ
โ y = 'd' (index 3) โ
โ โ
โ Check: find(2) == find(3)? โ
โ find(2): โ
โ parent[2] = 0 โ
โ parent[0] = 0 โ
(root) โ
โ return 0 โ
โ โ
โ find(3): โ
โ parent[3] = 3 โ
(root) โ
โ return 3 โ
โ โ
โ 0 == 3? NO! โ
โ
โ โ
โ Different groups! They can be different! โ
โ
โ Continue checking... โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ EQUATION 4: "a!=d" โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Extract: x = 'a' (index 0) โ
โ y = 'd' (index 3) โ
โ โ
โ Check: find(0) == find(3)? โ
โ find(0) = 0 โ
โ find(3) = 3 โ
โ โ
โ 0 == 3? NO! โ
โ
โ โ
โ Different groups! They can be different! โ
โ
โ Continue checking... โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
All != equations passed! โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ FINAL RESULT: TRUE โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ โ
โ All constraints can be satisfied! โ
โ
โ โ
โ Proof by assignment: โ
โ a = b = c = 1 (all in same group) โ
โ d = 2 (different group) โ
โ โ
โ Check: โ
โ a==b? 1==1 โ
โ
โ b==c? 1==1 โ
โ
โ c!=d? 1โ 2 โ
โ
โ a!=d? 1โ 2 โ
โ
โ โ
โ All equations satisfied! Return true! ๐ โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
๐ Key Observations:
-
Two phases essential: โ Process all == first to establish complete equality groups
-
Transitive equality automatic: ๐ Union-Find handles a==b, b==c โ a==c automatically
-
Same group = must be equal: ๐ฅ If find(x) == find(y), they're in same equality group
-
Different groups = can differ: โจ Variables in different groups can have different values
-
Space efficient: ๐ฆ Only 26 elements regardless of input size!
๐ Complexity Analysis
Time Complexity: O(n ร ฮฑ(n)) โก
Where:
n = number of equations
ฮฑ(n) = inverse Ackermann (โ O(1))
Phase 1 (process ==):
For each equation: O(ฮฑ(n)) for union
Total: O(n ร ฮฑ(n))
Phase 2 (check !=):
For each equation: O(ฮฑ(n)) for find
Total: O(n ร ฮฑ(n))
Overall: O(n ร ฮฑ(n)) โ O(n)
Example: n = 500
Operations: ~2500 (very fast!) โ
Space Complexity: O(1) ๐ฆ
Union-Find arrays: O(26) for 26 letters
26 is constant!
Space: O(1) ๐ฆ
Even with 1000 equations:
Still only 26 elements! โจ
Amazing space efficiency! ๐
๐ Pattern Recognition & Variations
Constraint Satisfaction Pattern ๐ฏ
// Template for constraint satisfaction problems
class Solution {
private int[] parent, rank;
public boolean satisfiable(Constraint[] constraints) {
// Initialize Union-Find
parent = new int[NUM_VARIABLES];
for (int i = 0; i < NUM_VARIABLES; i++) {
parent[i] = i;
}
// PHASE 1: Process equality constraints
// Build groups of variables that must be equal
for (Constraint c : constraints) {
if (c.type == EQUAL) {
union(c.var1, c.var2);
}
}
// PHASE 2: Validate inequality constraints
// Check no variable pairs are both equal AND not-equal
for (Constraint c : constraints) {
if (c.type == NOT_EQUAL) {
if (find(c.var1) == find(c.var2)) {
return false; // Contradiction!
}
}
}
return true; // All constraints satisfied!
}
private int find(int x) { /* path compression */ }
private void union(int x, int y) { /* union by rank */ }
}
When to Use This Pattern ๐ฏ
โ
Perfect for:
โข "Can constraints be satisfied?"
โข "Check consistency of equations"
โข "Validate relationships"
โข "Equality + inequality constraints"
โข "Transitive relationships"
๐ Recognition keywords:
โข "Satisfiability"
โข "Possible to satisfy"
โข "Consistent"
โข "Valid assignment"
โข "Equations with == and !="
๐ Pattern characteristics:
โข Two types of constraints (equal/not-equal)
โข Transitivity matters
โข Binary relationships
โข Yes/No answer (satisfiable or not)
Related LeetCode Problems ๐
Direct Applications:
-
Couples Holding Hands (LC 765) - Hard ๐ โข What's similar: Constraint satisfaction with swaps ๐ โข What's different: Count minimum swaps, not just check validity โ โข Key insight: Each wrong pair needs one swap! ๐ก
-
Sentence Similarity II (LC 737) - Medium ๐ โข What's similar: Transitive equality relationships ๐ โข What's different: String similarity, not variable equality โ โข Key insight: Union synonyms, check if words in same group! ๐ฏ
-
Most Stones Removed (LC 947) - Medium ๐ชจ โข What's similar: Union-Find to find connected components ๐ โข What's different: Grid-based connections, not equations โ โข Key insight: Remove all but one stone per component! ๐ก
๐ Quick Revision Notes
๐ฏ Core Concept
Satisfiability of Equality Equations checks if constraints can be satisfied using Union-Find ๐! Two-phase approach: Phase 1 - process all == equations to build equality groups via union ๐ค. Phase 2 - check all != equations; if both variables in same group โ contradiction! โ Otherwise satisfiable! โ
Transitivity handled automatically by Union-Find! ๐ If a==b and b==c, then a==c without explicit equation! Time: O(n ร ฮฑ(n)) โ O(n) โก, Space: O(1) - only 26 letters! ๐ฆ
โก Quick Implementation
public class Solution {
public boolean equationsPossible(String[] equations) {
// Step 1: create parent and rank arrays.
int[] parent = new int[26];
int[] rank = new int[26];
for (int i = 0; i < 26; i++) {
parent[i] = i;
rank[i] = 0;
}
// Step 2: process all == equations (for example, a==b).
// Get chars and create a common leader (or group)
for (String eq : equations) {
if (eq.charAt(1) == '=') {
int a = eq.charAt(0) - 'a';
int b = eq.charAt(3) - 'a';
union(a, b, parent, rank);
}
}
// Step 3: process all != equations (for example, a != b) .
for (String eq : equations) {
if (eq.charAt(1) == '!') {
int a = eq.charAt(0) - 'a';
int b = eq.charAt(3) - 'a';
if (find(a, parent) == find(b, parent)) {
return false;
}
}
}
return true;
}
private void union(int a, int b, int[] parent, int[] rank) {
int rootA = find(a, parent);
int rootB = find(b, parent);
// no action if they already share a common leader.
if (rootB == rootA) {
return;
}
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else {
parent[rootB] = rootA;
rank[rootA]++;
}
}
private int find(int i, int[] parent) {
if (parent[i] != i) {
parent[i] = find(parent[i], parent);
}
return parent[i];
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.equationsPossible(new String[] { "a==b", "b!=a" })); // false
System.out.println(s.equationsPossible(new String[] { "b==a", "a==b" })); // true
System.out.println(s.equationsPossible(new String[] { "a==b", "b==c", "a==c" })); // true
System.out.println(s.equationsPossible(new String[] { "a==b", "b!=c", "c==a" })); // false
}
}
๐ Key Insights
Two-Phase Strategy is Critical: ๐
Why process in two separate phases?
WRONG (single pass):
equations = ["c!=a", "a==b", "b==c"]
Process in order:
c!=a: Check find(c)==find(a)? NO โ
(looks OK)
a==b: union(a,b)
b==c: union(b,c) โ now a,b,c all equal!
But we already validated c!=a earlier!
Missed contradiction! โ
RIGHT (two phases):
Phase 1: Process ALL ==
a==b: union(a,b)
b==c: union(b,c) โ {a,b,c}
Complete equality groups established!
Phase 2: Check ALL !=
c!=a: find(c)==find(a)? YES! โ
CONTRADICTION detected!
Return false! โ
Two phases ensures complete transitivity! ๐ฏ
Transitivity Automatically Handled: ๐
Union-Find's superpower: Transitive closure!
Example:
a==b
b==c
c==d
No need to explicitly check a==d!
Union-Find automatically groups them:
union(a,b) โ {a,b}
union(b,c) โ {a,b,c}
union(c,d) โ {a,b,c,d}
All in same group! โ
All must be equal!
When we check "d!=a":
find(d)==find(a)? YES!
Contradiction! โ
Transitivity handled without extra code! ๐ฏ
Char to Index Mapping: ๐ค
Convert letters to array indices:
char c = 'b';
int index = c - 'a'; // 'b' - 'a' = 1
Mapping:
'a' โ 0
'b' โ 1
'c' โ 2
...
'z' โ 25
Why?
- Array access faster than HashMap
- Only 26 possible letters
- O(1) space regardless of input
- Clean and efficient! โก
Example:
equation = "a==b"
x = equation.charAt(0) - 'a' // 0
y = equation.charAt(3) - 'a' // 1
union(0, 1)
Same Group = Must Be Equal: ๐ฅ
The contradiction check:
if (find(x) == find(y)) {
// x and y have same root
// โ They're in same equality group
// โ They MUST be equal
// But equation says x!=y
// โ They must be DIFFERENT
// Contradiction! Return false โ
}
Example:
a==b (groups: {a,b})
b!=a (check: a and b in same group? YES!)
They must be equal (from a==b)
But they must be different (from b!=a)
Impossible! โ
๐ช Memory Aid
"First unite the equals true" ๐ค
"Then check not-equals too" ๐
"Same group means they're the same" ๐ฅ
"Contradiction ends the game!" โ โจ
โ ๏ธ Don't Forget
- Two phases required - process ALL == before checking ANY !=! ๐
- Char to index - use
c - 'a'for array access! ๐ค - Check eq.charAt(1) - '=' for ==, '!' for !=! ๐
- Variables at indices 0 and 3 - eq.charAt(0) and eq.charAt(3)! ๐
- Space O(1) - only 26 letters maximum! ๐ฆ
- Find before comparing - always find(x) == find(y), not x == y! ๐
๐ Congratulations!
You've mastered Union-Find for Constraint Satisfaction! ๐
What You Learned:
โ
Two-phase strategy - build groups first, validate second! ๐
โ
Constraint satisfaction - check if all constraints compatible! โ๏ธ
โ
Transitivity handling - automatic with Union-Find! ๐
โ
Contradiction detection - same group in != equation! โ
โ
Space optimization - O(1) for fixed alphabet! ๐ฆ
The Beautiful Pattern:
Union-Find Constraint Satisfaction:
Phase 1: Process positive constraints (==)
Build groups of related items
Transitivity handled automatically
Phase 2: Validate negative constraints (!=)
Check against established groups
Contradiction = items in same group but must differ
This pattern solves:
โ
Equation satisfiability
โ
Relationship consistency
โ
Constraint validation
โ
Binary constraint problems
โ
Any equal/not-equal checking
Four Union-Find patterns mastered:
1. Connected components (Problem 195) ๐ข
2. Cycle detection (Problem 198) ๐
3. Grouping by property (Problem 199) ๐
4. Constraint satisfaction (Problem 200) โ๏ธ
Union-Find complete toolkit! ๐
Twenty-three problems completed! ๐
Union-Find mastery expanded to constraint satisfaction! ๐ชโจ๐ฏ๐โ๏ธ