Most stones removed

Maximize removed stones by grouping those that share a row or column.

graphs dfs union-find connected-components

You are given a list `stones` of `(x, y)` integer coordinates representing the positions of stones on a 2D grid. In one move, you may remove a stone if it shares the same row or the same column with another stone that has not been removed yet. Write a function `max_removed(stones)` that returns the maximum number of stones that can be removed under this rule.

A stone can always be removed as long as there is at least one other stone with the same row or column remaining. You can remove stones in any order. The final set of stones must not be empty because if only one stone remains, there is nothing left to remove.

Implement the function exactly with the signature `def max_removed(stones):`.

Constraints

- `1 <= len(stones) <= 4000`
- Each coordinate `(x, y)` is an integer with `0 <= x, y <= 10^4`.
- All positions are distinct.
- Your solution must be O(N) or O(N log N) in time (depending on approach), O(N) space.

Hint: Stones that are connected via shared rows and columns form connected components. In each component of size `k`, you can always remove `k - 1` stones, leaving exactly one stone. So the answer is the total number of stones minus the number of connected components.

Example

```python
>>> max_removed([(0,0), (0,1), (1,1), (2,2)])
2
>>> max_removed([(0,0), (0,2), (1,1), (2,0), (2,2)])
3
```

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of each stone as a node that connects to other stones sharing the same row or column.

The rule 'can be removed if shares a row or column with another' means you can always reduce a connected component to a single stone.

Build an undirected graph where stones are nodes, and edges connect stones that share an x or y. Then count connected components.

The answer is `n - c` where `n` is the total number of stones and `c` is the number of connected components.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.