Problem Description

You are given n stones placed on a 2D coordinate plane. Each stone is positioned at an integer coordinate point [x, y], and no two stones can occupy the same position.

A stone can be removed from the plane if it shares either the same row (same x-coordinate) or the same column (same y-coordinate) with at least one other stone that hasn't been removed yet.

Given an array stones where stones[i] = [xi, yi] represents the position of the i-th stone, you need to find the maximum number of stones that can be removed.

For example, if you have stones at positions [0,0], [0,1], and [1,0]:

• Stone at [0,0] shares row 0 with [0,1] and column 0 with [1,0]
• Stone at [0,1] shares row 0 with [0,0]
• Stone at [1,0] shares column 0 with [0,0]

Since all stones are connected through shared rows or columns, you can remove 2 stones (leaving 1 remaining).

The key insight is that stones sharing rows or columns form connected groups. Within each connected group, you can remove all stones except one. The solution uses Union-Find to identify these connected components - stones in the same row or column are merged into the same component. The maximum removable stones equals the total number of successful union operations, which is equivalent to total stones - number of connected components.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem can be modeled as a graph where stones are nodes, and edges exist between stones that share the same row or column.

Is it a tree?

• No: The graph formed by stones is not necessarily a tree. It can have cycles (e.g., stones forming a rectangle pattern) and may consist of multiple disconnected components.

Is the problem related to directed acyclic graphs?

• No: The relationships between stones are undirected - if stone A shares a row/column with stone B, then B also shares that row/column with A.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between stones. We're trying to find connected components and determine the maximum number of removable stones.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - stones that share rows or columns form connected components, and within each component, all but one stone can be removed.

Disjoint Set Union

• Yes: DSU (Union-Find) is the suggested approach for handling connectivity problems efficiently.

Conclusion: The flowchart leads us to use Disjoint Set Union (DSU/Union-Find) for this connectivity problem. While the solution uses Union-Find rather than explicit DFS, the underlying concept is the same - we're exploring connected components in a graph. DFS could alternatively be used to identify connected components by traversing from each unvisited stone and marking all stones reachable through shared rows/columns.

Intuition

The key insight comes from understanding what makes a stone removable. A stone can be removed if it shares a row or column with another stone that hasn't been removed. This creates a dependency chain - as long as stones are connected through shared rows or columns, we can keep removing them until only one remains in that connected group.

Think of it this way: if we have stones at positions [0,0], [0,2], and [2,0], they form a connected component because:

• [0,0] and [0,2] share row 0
• [0,0] and [2,0] share column 0

In this connected component of 3 stones, we can remove 2 of them, leaving just 1.

This pattern holds for any connected component: if a component has k stones, we can remove exactly k-1 stones from it. The last stone in each component cannot be removed because it would have no other stones in its row or column.

Therefore, if we have n total stones divided into c connected components:

• Each component must keep 1 stone
• Total stones that must remain = c
• Maximum removable stones = n - c

To find these connected components, we can model the problem as a graph where stones are nodes and edges exist between stones sharing rows or columns. Union-Find is perfect for this because:

1. We can efficiently merge stones that share rows/columns into the same component
2. Each successful union operation represents one stone that can be removed
3. The total number of successful unions equals the maximum removable stones

The beauty of this approach is that we don't need to simulate the actual removal process - we just need to count how many stones can theoretically be removed based on the connectivity structure.

Learn more about Depth-First Search, Union Find and Graph patterns.

Solution Approach

The solution uses the Union-Find (Disjoint Set Union) data structure to efficiently track and merge connected components of stones.

Union-Find Implementation:

The UnionFind class maintains two arrays:

• p: Parent array where p[x] stores the parent of node x
• size: Size array to track the size of each component for optimization

The find(x) method locates the root of the component containing x, using path compression to optimize future lookups:

if self.p[x] != x:
    self.p[x] = self.find(self.p[x])  # Path compression
return self.p[x]

The union(a, b) method merges two components and returns True if they were previously separate (successful union) or False if already connected:

pa, pb = self.find(a), self.find(b)
if pa == pb:
    return False  # Already in same component

It uses union by size optimization - the smaller component is attached to the larger one to keep the tree balanced.

Main Algorithm:

1. Initialize a Union-Find structure with n nodes (one for each stone)

2. Use a nested loop to check all pairs of stones:

   for i, (x1, y1) in enumerate(stones):
       for j, (x2, y2) in enumerate(stones[:i]):

3. For each pair, check if they share a row (x1 == x2) or column (y1 == y2)

4. If stones share a row or column, attempt to union them:

   if x1 == x2 or y1 == y2:
       ans += uf.union(i, j)

5. Count successful unions - each successful union represents one stone that can be removed

The time complexity is O(n² × α(n)) where α is the inverse Ackermann function (practically constant), and space complexity is O(n) for the Union-Find structure.

The elegance of this approach is that we don't need to simulate the removal process. Each successful union operation directly corresponds to a removable stone, giving us the final answer.

Example Walkthrough

Let's walk through a concrete example with stones at positions: [[0,0], [0,2], [1,1], [2,0], [2,2]]

Step 1: Initialize Union-Find

• Create a Union-Find structure with 5 nodes (indices 0-4)
• Initially, each stone is its own component: p = [0, 1, 2, 3, 4]

Step 2: Check all pairs of stones

Examining stone pairs:

• Stones 0 [0,0] and 1 [0,2]: Share row 0 → Union(0,1) succeeds → Components: {0,1}, {2}, {3}, {4}
• Stones 0 [0,0] and 2 [1,1]: Different row and column → No union
• Stones 0 [0,0] and 3 [2,0]: Share column 0 → Union(0,3) succeeds → Components: {0,1,3}, {2}, {4}
• Stones 0 [0,0] and 4 [2,2]: Different row and column → No union
• Stones 1 [0,2] and 2 [1,1]: Different row and column → No union
• Stones 1 [0,2] and 3 [2,0]: Already connected through stone 0 → Union returns False
• Stones 1 [0,2] and 4 [2,2]: Share column 2 → Union(1,4) succeeds → Components: {0,1,3,4}, {2}
• Stones 2 [1,1] and 3 [2,0]: Different row and column → No union
• Stones 2 [1,1] and 4 [2,2]: Different row and column → No union
• Stones 3 [2,0] and 4 [2,2]: Share row 2, but already connected → Union returns False

Step 3: Count successful unions

• Total successful unions: 3
• This means we can remove 3 stones

Verification:

• We have 2 connected components:
  • Component 1: {0,1,3,4} - stones connected through shared rows/columns
  • Component 2: {2} - isolated stone at [1,1]
• From 5 stones with 2 components: max removable = 5 - 2 = 3 ✓

The stones could be removed in this order:

1. Remove stone 1 [0,2] (shares row with 0, column with 4)
2. Remove stone 3 [2,0] (shares column with 0, row with 4)
3. Remove stone 4 [2,2] (shares row with remaining stone 0)
4. Remaining stones: 0 [0,0] and 2 [1,1] cannot be removed

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × α(n))

The code uses a nested loop structure where:

• The outer loop iterates through all n stones with enumerate(stones)
• The inner loop iterates through all previous stones with enumerate(stones[:i]), which in the worst case iterates through i-1 stones
• This creates a total of 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n²) iterations

Within each iteration, the code performs:

• A comparison check (x1 == x2 or y1 == y2) which is O(1)
• A union operation which internally calls find twice

The find operation uses path compression and has an amortized time complexity of O(α(n)), where α(n) is the inverse Ackermann function. The union operation calls find twice and performs constant-time operations, so it's also O(α(n)).

Therefore, the overall time complexity is O(n²) × O(α(n)) = O(n² × α(n)).

Space Complexity: O(n)

The space usage consists of:

• The UnionFind data structure stores two arrays: self.p and self.size, each of size n
• The recursive call stack for find operation can go up to O(n) depth in the worst case before path compression
• Other variables (ans, loop indices) use O(1) space

The dominant space usage is O(n) for the UnionFind arrays, giving an overall space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Coordinate Mapping Confusion

A common mistake is trying to directly use coordinates as node indices in the Union-Find structure. Since coordinates can be large (up to 10^4), developers might attempt:

# WRONG: This could create a massive Union-Find structure
uf = UnionFind(10001 * 2)  # Trying to accommodate all possible x and y values
for x, y in stones:
    uf.union(x, y + 10001)  # Mapping y coordinates to avoid collision

Solution: Use stone indices (0 to n-1) as nodes in Union-Find, not the coordinates themselves. Each stone gets a unique index, and we connect indices of stones that share rows/columns.

2. Inefficient Component Counting

After building the Union-Find structure, developers often incorrectly count components:

# WRONG: This counts all unique parents, including non-root nodes
components = len(set(uf.parent))

# Also WRONG: Iterating through all possible coordinates
components = 0
for i in range(len(stones)):
    if uf.find(i) == i:
        components += 1

Solution: Count successful unions directly. Each successful union reduces the number of components by 1, so removable_stones = successful_unions = n - components.

3. Duplicate Pair Checking

Processing all pairs twice leads to incorrect counting:

# WRONG: This checks each pair twice (i,j) and (j,i)
for i in range(len(stones)):
    for j in range(len(stones)):
        if i != j and (stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]):
            result += uf.union(i, j)

Solution: Use triangular iteration to check each pair only once:

for i in range(len(stones)):
    for j in range(i):  # Only check previous stones
        # ... union logic

4. Missing Path Compression

Implementing Union-Find without path compression severely degrades performance:

# WRONG: No path compression
def find(self, x):
    while self.parent[x] != x:
        x = self.parent[x]
    return x

Solution: Always implement path compression to maintain near-constant time complexity:

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

5. Incorrect Answer Calculation

A subtle but critical error is returning the number of components instead of removable stones:

# WRONG: Returns number of components
components = len(set(uf.find(i) for i in range(len(stones))))
return components

# WRONG: Off by one error
return len(stones) - components - 1

Solution: The answer is exactly the number of successful unions, or equivalently total_stones - number_of_components. Track successful unions directly for clarity.