565. Most Stones Removed with Same Row or Column
There are n stones placed on a 2-D grid at integer coordinates, at most one stone per point; stones[i] = [xi, yi].
A stone may be removed if at least one other stone that is still on the grid shares its row or its column. Return the maximum number of stones you can remove.
Think of stones that share a row or column as connected — the answer only depends on how the stones group together.
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: All six stones chain together through shared rows and columns, forming one connected group. From any connected group you can peel stones off one at a time until a single stone remains, so 6 − 1 = 5 removals.
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: The four corner stones link up around the border (shared rows 0 and 2, shared columns 0 and 2), but the center stone at (1, 1) touches nothing. Two groups → 5 − 2 = 3 removals.
Constraints:
- 1 ≤ n ≤ 1000
- 0 ≤ x, y ≤ 10⁴
- No two stones occupy the same point.
Hints:
Try small cases: from any group of stones that is connected through shared rows/columns, how many can you always remove? (Remove outlying stones first, working inward.)
The answer is n minus the number of connected components. Now the problem is just: count components among stones connected by shared row OR column.
You never need stone-to-stone edges. Give every row and every column its own node in a union-find, and union row x with column y for each stone — stones in the same component share a root.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Expected output: 5