LeetCode 947: Most Stones Removed with Same Row or Column

Problem Restatement

We are given stones on a 2D plane.

Each stone has coordinates:

[x, y]

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

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

Function shape:

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

Examples

Example 1:

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:

5

Example 2:

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

There are two connected groups:

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:

3

Example 3:

stones = [[0,0]]

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

Answer:

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:

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:

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:

(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:

len(stones) - components

Walkthrough

Use:

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

Connections include:

[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:

n = 6
components = 1

Answer:

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:

total removable = n - number_of_components

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

Complexity

Let:

n = len(stones)

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

Implementation

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:

self.parent = list(range(n))

find returns the representative of a component:

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

Path compression shortens future lookups:

self.parent[x] = self.parent[self.parent[x]]

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

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

After all unions, we count unique component roots:

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

The final answer is:

return n - components

Testing

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