Most Stones Removed with Same Row or Column

▶

Steps

setup

Initialize UnionFind Structure

Create an empty union-find structure with no parents or ranks. The count of connected components is zero.

💡 Initialization is crucial to track each unique node (row or column) and their connected components.

Line:

uf = UnionFind()

💡 UnionFind starts empty; no nodes or unions exist yet.

union

Process Stone [0,0]: Union Row 0 and Column 10000

Union operation is called for row 0 and column 0 offset by 10000 (10000). Both nodes are created and connected.

💡 Each stone connects a row node and a column node, building the union-find graph.

Line:

uf.union(0, 0 + OFFSET)

💡 New connected component formed with nodes 0 and 10000 linked.

union

Process Stone [0,1]: Union Row 0 and Column 10001

Union operation is called for row 0 and column 1 offset by 10000 (10001). Column node 10001 is created and connected to existing row node 0.

💡 Union by rank attaches the new column node to the existing row node's component.

Line:

uf.union(0, 1 + OFFSET)

💡 Row 0 now connects to two columns, expanding the component.

union

Process Stone [1,0]: Union Row 1 and Column 10000

Union operation is called for row 1 and column 0 offset by 10000 (10000). Row node 1 is created and connected to existing column node 10000.

💡 Connecting a new row to an existing column merges their components.

Line:

uf.union(1, 0 + OFFSET)

💡 Row 1 and Row 0 become connected through column 0.

union

Process Stone [1,2]: Union Row 1 and Column 10002

Union operation is called for row 1 and column 2 offset by 10000 (10002). Column node 10002 is created and connected to row 1.

💡 Adding a new column node connected to an existing row expands the component.

Line:

uf.union(1, 2 + OFFSET)

💡 Row 1 now connects to two columns, increasing component size.

union

Process Stone [2,1]: Union Row 2 and Column 10001

Union operation is called for row 2 and column 1 offset by 10000 (10001). Row node 2 is created and connected to existing column node 10001.

💡 Connecting a new row to an existing column merges their components.

Line:

uf.union(2, 1 + OFFSET)

💡 Row 2 connects to the component containing row 0 via column 10001.

union

Process Stone [2,2]: Union Row 2 and Column 10002

Union operation is called for row 2 and column 2 offset by 10000 (10002). Both nodes exist; union merges their components if separate.

💡 Union by rank attaches smaller tree under larger, reducing component count.

Line:

uf.union(2, 2 + OFFSET)

💡 All stones are now connected in one or two components, reflecting shared rows/columns.

traverse

Find Number of Connected Components

After all unions, the union-find count reflects the number of connected components formed by rows and columns.

💡 The count helps determine how many stones can be removed by counting components.

Line:

return len(stones) - uf.count

💡 Connected components represent groups of stones connected by rows or columns.

reconstruct

Calculate Final Answer: Stones Removed

Calculate the maximum stones that can be removed as total stones minus number of connected components.

💡 This formula works because each connected component must leave at least one stone.

Line:

return len(stones) - uf.count

💡 The answer 5 means 5 stones can be removed, leaving one stone per connected component.

reconstruct

Final State: Answer is 5 Stones Removed

The union-find count is 1, so maximum stones removed is 6 stones minus 1 component = 5.

💡 This confirms the algorithm's correctness and the meaning of union-find count.

Line:

return len(stones) - uf.count

💡 The union-find structure successfully grouped stones to compute the answer.

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.count = 0

    def find(self, x):
        if x not in self.parent:  # STEP 1: Initialize node
            self.parent[x] = x
            self.rank[x] = 0
            self.count += 1
        if self.parent[x] != x:  # STEP 2: Path compression
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)  # STEP 3: Find root of x
        rootY = self.find(y)  # STEP 4: Find root of y
        if rootX != rootY:  # STEP 5: Union by rank
            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
            self.count -= 1


def removeStones(stones):
    uf = UnionFind()  # STEP 1
    OFFSET = 10000
    for x, y in stones:  # STEP 2: For each stone
        uf.union(x, y + OFFSET)  # STEP 3: Union row and column
    return len(stones) - uf.count  # STEP 4: Calculate answer

if __name__ == '__main__':
    stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
    print(removeStones(stones))  # Output: 5

📊

Most Stones Removed with Same Row or Column - Watch the Algorithm Execute, Step by Step

Watching the union-find operations step-by-step reveals how connected components form dynamically, which is hard to grasp from code alone.

Visiting: none

Visiting: 0

Edge: 0 → 10000

0

10000

Visiting: 0

Edge: 0 → 10001

0

10000

10001

Visiting: 1

Edge: 1 → 10000

0

1

10000

10001

Visiting: 1

Edge: 1 → 10002

0

1

10000

10001

10002

Visiting: 2

Edge: 2 → 10001

0

1

2

10000

10001

10002

Visiting: 2

Edge: 2 → 10002

0

1

2

10000

10001

10002

Visiting: none

0

1

2

10000

10001

10002

Visiting: none

0

1

2

10000

10001

10002

Visiting: none

0

1

2

10000

10001

10002

Key Takeaways

✓ Union-Find efficiently groups stones connected by rows or columns into connected components.

This grouping is hard to visualize from code alone but becomes clear when watching nodes and unions form.

✓ Each stone connects a row node and a column node, and union operations merge these nodes into components.

Understanding this mapping clarifies why union-find is a natural fit for this problem.

✓ The final answer is total stones minus the number of connected components, reflecting that one stone per component must remain.

This insight links the union-find structure directly to the problem's solution.

Practice

1. You are given a list of user accounts, each with a username and multiple email addresses. Some accounts may belong to the same user if they share at least one email address. Which algorithmic approach best guarantees merging all accounts belonging to the same user efficiently?

easy

A. Greedy approach that merges accounts by comparing usernames only

B. Dynamic programming to find the longest common subsequence of emails

C. Brute force nested loops checking every pair of accounts for email overlap

D. Union-Find data structure to group emails that appear in multiple accounts

Solution

1. Step 1: Understand the problem structure

   The problem requires grouping accounts by shared emails, which naturally forms connected components in a graph where emails are nodes.

2. Step 2: Identify the suitable algorithm

   Union-Find efficiently merges sets of emails that belong to the same user, handling multiple overlaps without redundant comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Union-Find is the classic pattern for merging overlapping sets [OK]

Hint: Accounts merge is a connected components problem [OK]

Common Mistakes:

• Merging by username only misses shared emails
• Brute force is too slow for large inputs

2. 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

3. Examine the following buggy Union-Find code snippet for the network connectivity problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with 'return self.find(self.parent[x])' in find method

B. Line 'self.count = n' in __init__ method

C. Line 'self.rank[rootX] += 1' in union method

D. Line 'self.parent[rootX] = rootY' in union method

Solution

1. Step 1: Identify path compression implementation

   The find method should assign the parent during recursion: self.parent[x] = self.find(self.parent[x]) to flatten the tree.

2. Step 2: Understand impact of missing assignment

   Without path compression, find operations become slower and can cause TLE or incorrect component counts on large inputs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing path compression assignment is a classic subtle bug [OK]

Hint: Path compression requires assignment to parent during find [OK]

Common Mistakes:

• Forgetting path compression assignment
• Misplacing rank increment
• Incorrectly decrementing count

4. Suppose the Accounts Merge problem is extended so that emails can be reused across multiple users (e.g., shared family emails). Which modification to the union-find approach correctly handles this scenario?

hard

A. Use a graph with edges between accounts and emails, then find connected components allowing multiple parents

B. Keep union-find as is; emails connected once belong to a single user

C. Modify union-find to allow multiple parents per node to represent shared emails

D. Assign emails to users greedily by first occurrence, ignoring overlaps

Solution

1. Step 1: Understand the new constraint

   Emails can belong to multiple users, so union-find's single parent per node model breaks down.

2. Step 2: Choose correct data structure

   A bipartite graph connecting accounts and emails with connected components allows shared emails without forcing merges.

3. Step 3: Evaluate other options

   Union-find cannot represent multiple parents; greedy assignment loses correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Graph approach models shared emails correctly [OK]

Hint: Union-find assumes disjoint sets; shared emails break this [OK]

Common Mistakes:

• Trying to modify union-find for multiple parents
• Ignoring shared emails and merging incorrectly

5. Suppose the problem is extended so that the input matrix isConnected can be updated dynamically with new connections added over time. Which data structure or approach is best suited to efficiently maintain and query the number of provinces after each update?

hard

A. Re-run DFS from scratch after each update to count provinces

B. Use Union-Find (Disjoint Set Union) with path compression to merge sets

C. Maintain adjacency list and run BFS only on updated nodes

D. Use a priority queue to track connected components sizes

Solution

1. Step 1: Understand dynamic updates require efficient merges

   Recomputing connected components from scratch is costly for each update.

2. Step 2: Identify data structure supporting fast union and find

   Union-Find with path compression supports near O(1) merges and queries, ideal for dynamic connectivity.

3. Step 3: Evaluate other options

   BFS or DFS on updates is expensive; priority queue does not maintain connectivity efficiently.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Union-Find is standard for dynamic connectivity problems [OK]

Hint: Dynamic connectivity -> Union-Find with path compression [OK]

Common Mistakes:

• Re-running DFS each update
• Trying BFS on partial graph