Remove the Maximum Number of Connected Stones

Problem Statement

On a 2D plane, we place n stones at distinct integer coordinates stones[i] = [r_i, c_i].

In a single move, you can remove a stone if there is currently at least one other stone remaining that shares either the same row (r_i) or the same column (c_i).

Return the maximum number of stones that can be removed.

Function Signature

def maxRemoveStones(stones: list[list[int]]) -> int:
    pass

Input & Output

• Input: A 2D list of integers stones of size n x 2, where each element [r_i, c_i] represents the 0-indexed coordinates of a stone.
• Output: An integer representing the maximum number of stones that can be removed.

Constraints

• 1 <= stones.length <= 1,000
• 0 <= r_i, c_i <= 10,000
• All [r_i, c_i] coordinates in stones are unique.

Examples

Example 1

Input: stones = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]
Output: 5
Explanation:
One optimal sequence of removals:
1. Remove [2, 2] (shares column 2 with [1, 2])
2. Remove [1, 2] (shares row 1 with [1, 0])
3. Remove [2, 1] (shares column 1 with [0, 1])
4. Remove [1, 0] (shares row 1 with none remaining, but shares column 0 with [0, 0])
5. Remove [0, 1] (shares row 0 with [0, 0])
Only stone [0, 0] remains. Total stones removed = 5.

Example 2

Input: stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]
Output: 3
Explanation:
Stones at [0, 0], [0, 2], [2, 0], and [2, 2] form a connected group and 3 can be removed, leaving 1.
The stone at [1, 1] shares no row or column with any other stone and cannot be removed.
Total stones removed = 3 + 0 = 3.

Example 3

Input: stones = [[0, 0]]
Output: 0
Explanation: There is only one stone, so no removals can be made.

Edge Cases

• A single stone: Cannot be removed; answer is 0.
• Completely disconnected stones: Each stone in its own row/column; answer is 0.
• All stones on a single line (row or column): Can remove n - 1 stones.