# LeetCode 947: Most Stones Removed with Same Row or Column

## Problem Restatement

We are given stones on a 2D plane.

Each stone has coordinates:

```python
[x, y]
```

A stone can be removed if there is another stone still on the plane that shares either:

```text
same row
same column
```

Return the maximum number of stones that can be removed.

The official statement asks for the largest possible number of removable stones, where each coordinate contains at most one stone.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of stone coordinates |
| Output | Maximum number of stones removable |
| Same row | Same `x` coordinate |
| Same column | Same `y` coordinate |
| Constraint | `1 <= stones.length <= 1000` |

Function shape:

```python
class Solution:
    def removeStones(self, stones: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

```python
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
```

All stones are connected through shared rows or columns.

We can remove all except one.

Answer:

```python
5
```

Example 2:

```python
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
```

There are two connected groups:

```text
group 1: [0,0], [0,2], [2,0], [2,2]
group 2: [1,1]
```

From the first group, we can remove `3` stones and leave one.

From the second group, we cannot remove the only stone.

Answer:

```python
3
```

Example 3:

```python
stones = [[0,0]]
```

There is only one stone, so it cannot be removed.

Answer:

```python
0
```

These are the standard examples for the problem.

## First Thought: Simulate Removals

One idea is to repeatedly remove any stone that shares a row or column with another remaining stone.

But the order of removal can be confusing.

Instead of simulating removals, we should ask which stones are connected.

If stones are connected by shared rows or columns, then inside that connected component we can remove every stone except one.

So the answer is:

```text
number of stones - number of connected components
```

## Key Insight

Model the stones as a graph.

Each stone is a node.

There is an edge between two stones if they share the same row or the same column.

Inside each connected component of size `k`, we can remove exactly:

```text
k - 1
```

stones.

One stone must remain, because the last stone in that component would have no other stone sharing its row or column.

Summing over all components gives:

```text
(k1 - 1) + (k2 - 1) + ... = n - components
```

So the task becomes counting connected components.

## Algorithm

Use union-find.

Each stone starts as its own component.

For every pair of stones:

1. If they share a row or column, union them.
2. After all unions, count how many distinct roots exist.
3. Return:

```python
len(stones) - components
```

## Walkthrough

Use:

```python
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
```

Connections include:

```text
[0,0] with [0,1]
[0,0] with [1,0]
[1,2] with [2,2]
[2,1] with [2,2]
[0,1] with [2,1]
```

Through these connections, all stones belong to one component.

So:

```text
n = 6
components = 1
```

Answer:

```python
6 - 1 = 5
```

## Correctness

Two stones belong to the same connected component exactly when we can move from one to the other through a chain of stones sharing rows or columns.

The union-find algorithm unions every pair of stones that directly shares a row or column. Therefore, after all unions, two stones have the same root exactly when they are in the same connected component.

In a connected component with `k` stones, at least one stone must remain. The final remaining stone cannot be removed because no other stone from that component remains to share a row or column with it.

Also, we can remove `k - 1` stones from a connected component. Since the component is connected, there is always a way to remove stones while keeping at least one neighboring relation available until only one stone remains.

Therefore, each component contributes exactly `k - 1` removable stones.

Summing over all components gives:

```text
total removable = n - number_of_components
```

The algorithm computes this value, so it returns the maximum number of stones removable.

## Complexity

Let:

```python
n = len(stones)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2 * α(n))` | We check every pair and union connected stones |
| Space | `O(n)` | Union-find arrays |

`α(n)` is the inverse Ackermann function, effectively constant for practical input sizes.

## Implementation

```python
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]

class Solution:
    def removeStones(self, stones: list[list[int]]) -> int:
        n = len(stones)
        dsu = DSU(n)

        for i in range(n):
            x1, y1 = stones[i]

            for j in range(i + 1, n):
                x2, y2 = stones[j]

                if x1 == x2 or y1 == y2:
                    dsu.union(i, j)

        components = len({dsu.find(i) for i in range(n)})

        return n - components
```

## Code Explanation

Each stone begins in its own component:

```python
self.parent = list(range(n))
```

`find` returns the representative of a component:

```python
def find(self, x: int) -> int:
```

Path compression shortens future lookups:

```python
self.parent[x] = self.parent[self.parent[x]]
```

For every pair of stones, we check whether they share a row or column:

```python
if x1 == x2 or y1 == y2:
    dsu.union(i, j)
```

After all unions, we count unique component roots:

```python
components = len({dsu.find(i) for i in range(n)})
```

The final answer is:

```python
return n - components
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.removeStones([
        [0, 0],
        [0, 1],
        [1, 0],
        [1, 2],
        [2, 1],
        [2, 2],
    ]) == 5

    assert s.removeStones([
        [0, 0],
        [0, 2],
        [1, 1],
        [2, 0],
        [2, 2],
    ]) == 3

    assert s.removeStones([
        [0, 0],
    ]) == 0

    assert s.removeStones([
        [0, 0],
        [1, 1],
        [2, 2],
    ]) == 0

    assert s.removeStones([
        [0, 1],
        [1, 0],
        [1, 1],
    ]) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example 1 | One large component |
| Standard example 2 | Multiple components |
| Single stone | Nothing removable |
| No shared row or column | No stones removable |
| Small connected group | Remove all but one |