Most Stones Removed with Same Row or Column
Medium · union find
Some stones lie on a big grid. The list stones gives each stone as a pair [row, col], and no two stones are on the same square.
You may remove a stone at any moment when another stone that has not been removed yet lies in the same row or in the same column as it. Stones can be removed in any order you like.
Return the largest number of stones you can remove.
Examples
Example 1
Input: stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]
Output: 3
Remove the stones at (0, 2), (2, 2) and (2, 0) in that order, each time another stone shares a row or column. The stones at (0, 0) and (1, 1) share nothing, so they stay.
Example 2
Input: stones = [[0, 0], [1, 1], [2, 2]]
Output: 0
No two stones share a row or a column, so none can be removed.
Example 3
Input: stones = [[4, 7]]
Output: 0
A lone stone has nothing to share with.
Constraints
- 1 <= len(stones) <= 1000
- 0 <= row, col <= 10^4
- No two stones have the same row and the same column.