Maximize Stone Removals Using Shared Rows or Columns
Company: PhonePe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Each pair in `stones` is a distinct occupied integer coordinate. You may remove a stone only while another remaining stone shares its row or its column. Return the largest total number of removals possible.
```cpp
class Solution {
public:
int removeStones(vector<vector<int>>& stones);
};
```
### Examples
**Example 1:**
```text
Input: stones = [[1,1],[1,3],[4,3],[8,8]]
Output: 2
Explanation: Remove[4,3] using[1,3], then[1,3] using[1,1]. The isolated[8,8] and one stone of the other component must remain.
```
**Example 2:**
```text
Input: stones = [[2,0],[2,2],[2,5]]
Output: 2
Explanation: All three share a row, so any two can be removed while keeping the last.
```
### Constraints
- `1 <= stones.length <= 1000`.
- `0 <= x_i,y_i <= 10^4`.
- No coordinate pair occurs twice.
### Contract considerations
Coordinates are unique, but row or column values may repeat many times.
```hint Read the boundary condition
In a connected group of stones, can you remove all but one using a spanning tree?
```
### Boundary reminders
Coordinates are unique, but row or column values may repeat many times.
Overview: Maximize Stone Removals Using Shared Rows or Columns. Each pair in stones is a distinct occupied integer coordinate.