1. Satisfiability of Equality Equations (LeetCode)
Model answer
The task
Given equations involving lowercase single-letter variables and equality or inequality, determine whether all equations can hold simultaneously.
Key idea
First merge variables that must be equal using a disjoint-set union (DSU). Then check every inequality: if its two variables are in the same set, the equations are inconsistent.
Approach
- Initialize each letter as its own DSU set.
- For every equality, union the sets of its two variables.
- For every inequality, compare the roots of its variables.
- Return
Falseif any inequality’s variables share a root; otherwise returnTrue.
class Solution:
def equationsPossible(self, equations: list[str]) -> bool:
parent = list(range(26))
rank = [0] * 26
def find(x: int) -> int:
# Path compression keeps trees shallow.
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a: int, b: int) -> None:
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return
# Union by rank keeps trees shallow.
if rank[root_a] < rank[root_b]:
parent[root_a] = root_b
elif rank[root_a] > rank[root_b]:
parent[root_b] = root_a
else:
parent[root_b] = root_a
rank[root_a] += 1
# Apply all required equalities before checking inequalities.
for equation in equations:
if equation[1:3] == "==":
a = ord(equation[0]) - ord("a")
b = ord(equation[3]) - ord("a")
union(a, b)
for equation in equations:
if equation[1:3] == "!=":
a = ord(equation[0]) - ord("a")
b = ord(equation[3]) - ord("a")
if find(a) == find(b):
return False
return True
Complexity:
- Time: O(n α(26)), where n is the number of equations and α is the inverse Ackermann function.
- Space: O(1), since the DSU stores a fixed number of lowercase letters.
Common follow-ups
- What if variables are arbitrary strings? Map each distinct variable to a DSU index.
- What if equations arrive incrementally? Add equalities to the DSU as they arrive; an inequality can be checked against the current sets.
- Why process equalities before inequalities? A later equality can connect variables that an earlier inequality would otherwise appear to permit.