Satisfiability of Equality Equations

▶

Steps

setup

Initialize Union-Find

Create union-find sets for all variables 'a' through 'z', each initially its own parent with rank 0.

💡 Initialization sets up each variable as a separate set, preparing for unions.

Line:

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)}

💡 Each variable starts isolated, so no contradictions exist yet.

traverse

Process first equality: 'a==b'

Start processing the first equation 'a==b'. Since it is an equality, prepare to union sets containing 'a' and 'b'.

💡 Union operations merge sets of variables that must be equal.

Line:

for eq in equations:
    if eq[1:3] == '==':
        uf.union(eq[0], eq[3])

💡 Union will connect 'a' and 'b' in the union-find structure.

traverse

Find root of 'a'

Find the root parent of 'a'. Since 'a' is its own parent, root is 'a'.

💡 Finding root helps determine which sets to union.

Line:

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

💡 'a' is currently a root of its own set.

traverse

Find root of 'b'

Find the root parent of 'b'. Since 'b' is its own parent, root is 'b'.

💡 Finding root of 'b' prepares for union with 'a'.

Line:

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

💡 'b' is currently a root of its own set.

union

Union sets of 'a' and 'b'

Since roots of 'a' and 'b' differ, union their sets by making 'b' point to 'a' and incrementing rank of 'a'.

💡 Union merges two sets, reflecting equality between variables.

Line:

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

💡 Union-find tree updated to reflect 'a' and 'b' are connected.

traverse

Process second equation: 'b!=a'

Now process the inequality 'b!=a'. We must check if 'b' and 'a' are connected in union-find.

💡 Inequalities require checking if variables are in the same set to detect contradictions.

Line:

for eq in equations:
    if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):
        return False

💡 If roots match, inequality contradicts equality.

traverse

Find root of 'b' for inequality check

Find root of 'b' to check if it matches root of 'a'. Root is 'a' due to previous union.

💡 Finding root confirms which set 'b' belongs to.

Line:

uf.find(eq[0])

💡 'b' root is 'a', same as 'a'.

traverse

Find root of 'a' for inequality check

Find root of 'a' to compare with root of 'b'. Root is 'a'.

💡 Comparing roots determines if inequality contradicts equality.

Line:

uf.find(eq[3])

💡 'a' root is 'a', same as 'b'.

prune

Detect contradiction and return false

Since 'b' and 'a' share the same root but the equation says 'b!=a', a contradiction is detected and the function returns false.

💡 Early contradiction detection stops unnecessary further checks.

Line:

if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):
    return False

💡 Union-find efficiently detects conflicts between equality and inequality.

prune

Final answer: false

The algorithm returns false because the inequality contradicts the equality union-find structure.

💡 The final output reflects the contradiction detected.

Line:

return False

💡 Union-find quickly detects unsatisfiable equations.

class UnionFind:
    def __init__(self):
        # STEP 1: Initialize parents and ranks
        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):
        # STEP 3 & 4 & 7 & 8: Find root with path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # STEP 2 & 5: Union sets of x and 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()  # STEP 1
    for eq in equations:  # STEP 2
        if eq[1:3] == '==':
            uf.union(eq[0], eq[3])
    for eq in equations:  # STEP 6
        if eq[1:3] == '!=' and uf.find(eq[0]) == uf.find(eq[3]):
            return False  # STEP 9 & 10
    return True

📊

Satisfiability of Equality Equations - Watch the Algorithm Execute, Step by Step

Watching each union and find operation visually reveals how contradictions arise early, making the algorithm efficient and intuitive.

Visiting: none

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Visiting: a

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Queue / Stack

ab

Visiting: a

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Queue / Stack

a

Visiting: b

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Queue / Stack

b

Visiting: none

Edge: a → b

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Visiting: b

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Queue / Stack

ba

Visiting: b

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Queue / Stack

a

Visiting: a

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Visiting: none

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Visiting: none

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Key Takeaways

✓ Union-Find efficiently groups variables connected by equality, enabling quick contradiction detection.

This insight is hard to see from code alone because the union-find structure's dynamic grouping is abstract without visualization.

✓ Early contradiction detection stops processing as soon as an inequality conflicts with existing unions.

Visualizing this early stop clarifies why the algorithm is optimal and avoids unnecessary work.

✓ Path compression during find operations flattens the union-find tree, speeding up future queries.

Seeing the parent pointers update during find helps understand why union-find is so efficient.

Practice

1. Given the following code snippet implementing union-find for accounts merge, what is the final output of accountsMerge when called with accounts = [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]?

easy

A. [["John", "[e-mail]", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]

B. [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]", "[e-mail]"], ["Mary", "[e-mail]"]]

C. [["John", "[e-mail]", "[e-mail]"], ["John", "[e-mail]"], ["Mary", "[e-mail]"]]

D. [["Mary", "[e-mail]"], ["John", "[e-mail]", "[e-mail]", "[e-mail]"]]

Solution

1. Step 1: Trace union operations

   All emails in John's accounts are unioned: "[e-mail]", "[e-mail]", and "[e-mail]" become one set.

2. Step 2: Group emails by root and sort

   Mary's email is separate. John's merged emails are sorted alphabetically.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   John's emails merged correctly; Mary's account unchanged [OK]

Hint: Union-find merges all connected emails into one set [OK]

Common Mistakes:

• Forgetting to union all emails in an account
• Not sorting emails before output

2. Consider the following Python code implementing Union-Find with path compression and union by rank to find a redundant connection. Given the input edges [[1, 2], [1, 3], [2, 3]], what is the output of the function?

easy

A. [1, 2]

B. [1, 3]

C. [2, 3]

D. None (no redundant edge)

Solution

1. Step 1: Trace union operations for edges [1,2], [1,3], [2,3]

   Union(1,2) succeeds, Union(1,3) succeeds, Union(2,3) fails because 2 and 3 are already connected.

2. Step 2: Identify returned edge

   The first edge that causes union to fail is [2,3], so it is returned as redundant.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-Find detects cycle at edge [2,3] [OK]

Hint: Union fails when both nodes share the same root [OK]

Common Mistakes:

• Returning first edge instead of the one causing cycle
• Confusing union success/failure
• Off-by-one indexing errors

3. What is the time complexity of the optimal union-find based solution for the Accounts Merge problem, where N is the number of accounts and M is the maximum number of emails per account?

medium

A. O(N^2 * M) because each account is compared with every other

B. O(N * M^2) due to nested loops over emails

C. O(N * M * α(N * M)) where α is the inverse Ackermann function

D. O(N * M log (N * M)) due to sorting emails after union

Solution

1. Step 1: Identify union-find operations cost

   Union-find operations (union/find) run in nearly O(1) amortized time, specifically O(α(N*M)) per operation.

2. Step 2: Count total operations

   We perform union operations for each email in each account, totaling O(N*M) unions and finds.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Union-find with path compression yields almost linear time [OK]

Hint: Union-find nearly linear with inverse Ackermann factor [OK]

Common Mistakes:

• Confusing sorting cost with union-find cost
• Assuming quadratic due to nested loops

4. What is the time complexity of the optimal union-find approach for the Swim in Rising Water problem on an n x n grid, where n is the grid dimension?

medium

A. O(n^2 log n) due to sorting all n^2 cells and near-constant union-find operations

B. O(n^4) due to nested loops over grid and union operations

C. O(n^2 * maxElevation) because of simulating water rise for each elevation

D. O(n^2) because each cell is processed once with union-find operations

Solution

1. Step 1: Identify main operations

   Sorting all n^2 cells takes O(n^2 log n^2) = O(n^2 log n). Union-find operations are almost O(1) amortized per union/find.

2. Step 2: Combine complexities

   Total complexity dominated by sorting: O(n^2 log n). Union-find merges add negligible overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates; union-find nearly constant time per operation [OK]

Hint: Sorting n^2 cells dominates complexity [OK]

Common Mistakes:

• Assuming union-find operations cost O(log n) each
• Confusing brute force simulation complexity with optimal
• Ignoring sorting cost or treating union-find as O(1) without justification

5. Suppose the problem is modified so that edges can be reused multiple times (i.e., multi-edges allowed), and we want to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob. Which modification to the optimal union-find approach is necessary?

hard

A. Use a multigraph union-find variant that counts edge multiplicities and only removes redundant edges after full connectivity.

B. Switch to a shortest path algorithm since union-find cannot handle multi-edges.

C. No change needed; the original union-find approach works as is.

D. Process edges in arbitrary order without sorting since multi-edges guarantee connectivity.

Solution

1. Step 1: Understand multi-edge impact

   Multi-edges mean multiple edges connect same nodes; union-find alone merges sets once, ignoring multiplicity.

2. Step 2: Modify union-find approach

   Need to track edge counts per connection and only remove edges that do not break connectivity, requiring a multigraph-aware union-find or additional bookkeeping.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Original union-find ignores multiplicity -> must track edge counts [OK]

Hint: Union-find merges sets once; multi-edges require counting edges [OK]

Common Mistakes:

• Assuming union-find handles multi-edges without change
• Ignoring edge multiplicity
• Switching to unrelated algorithms unnecessarily