Remove the Maximum Number of Connected Stones
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# 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
```text
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
```text
Input: [[0, 0], [1, 1]]
Output: 0
```
The stones share neither a row nor a column, so neither can be removed.
Overview: Find the maximum stones removable when each move requires another remaining stone in the same row or column. The prompt defines unique coordinates, transitive connectivity, bounded inputs, and exact connected and isolated examples for later cross-language console verification.
Read the full Snapchat Software Engineer interview experience this question came from
Each stone occupies a unique integer [row, column] coordinate. In one move, remove a stone only when another currently remaining stone shares its row or column. Return the maximum possible number of removals. Stones are connected transitively through paths of shared rows or columns.
Constraints
- 1 <= len(stones) <= 1,000
- Each stone is [row, column] with both coordinates in [0, 10,000].
- No two stones occupy the same coordinate.
- A removal requires another currently remaining stone in the same row or column.
Examples
Input: ([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]],)
Expected Output: 5
Explanation: All six stones form one shared-row-or-column component, so one remains.
Input: ([[0, 0], [1, 1]],)
Expected Output: 0
Explanation: Two isolated components each retain their only stone.
Hints
- Count connected components under shared-row-or-column edges.
- Only one representative per previously seen row and column is needed to union the whole component.