Remove the Maximum Number of Connected Stones

Implement max_removed_stones(stones). Each stone occupies a unique integer coordinate [row, column] on a two-dimensional grid.

In one move, remove a stone if at least one other stone currently remaining shares its row or its column. Return the maximum number of stones that can be removed through a valid sequence of moves.

Function Contract

max_removed_stones(stones: list[list[int]]) -> int

Constraints

• 1 <= len(stones) <= 1000
• 0 <= row, column <= 10000
• No two stones occupy the same coordinate.
• Sharing a row or column is transitive only through paths of stones; stones need not share a coordinate directly with every stone in their connected group.

Examples

Example 1

Input: [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]
Output: 5

All six stones belong to one connected group under shared rows or columns, so exactly one stone must remain.

Example 2

Input: [[0, 0], [1, 1]]
Output: 0

The stones share neither a row nor a column, so neither can be removed.

Remove the Maximum Number of Connected Stones

Hints

1. Count connected components under shared-row-or-column edges.
2. Only one representative per previously seen row and column is needed to union the whole component.

Approach

Treat stones as graph vertices, joining two stones when they share a row or column. Within every connected component, removals can continue until exactly one stone remains, and the last stone cannot be removed. Thus the answer is the number of stones minus the number of components. Union each stone with the first earlier stone seen in its row and column; transitivity connects every relevant pair without constructing all quadratic edges.

• Time complexity: O(n alpha(n)) expected time, where n is the number of stones.
• Space complexity: O(n) for disjoint-set arrays and row/column maps.