Most Stones Removed with Same Row or Column
Medium · Graphs · Hash Table · Depth-First Search · Union Find · Graph
Problem
n stones sit on distinct integer points of a 2D plane; stones[i] = [x, y] is the position of stone i.
You may remove a stone only if another stone that is still on the board shares its row or its column. Return the largest number of stones you can remove.
Examples
Input: stones = [[0,0],[0,2],[1,2],[3,3]] Output: 2
The first three stones form one group that shrinks to one stone; [3,3] is alone.
Input: stones = [[1,1],[2,2],[3,3]] Output: 0
No two stones share a row or a column.
Input: stones = [[0,0],[0,1],[0,2],[1,0]] Output: 3
All four stones are linked, so only one has to stay.
Constraints
- 1 <= len(stones) <= 1000
- 0 <= x, y <= 10^4
- No two stones share the same point
Approaches
- Search over stones, comparing every pair — time O(n²), space O(n)
Follow-up
Can you also return an order of removals that achieves the maximum? Search each group from any stone; removing its stones in reverse order of discovery always leaves a stone that shares a line with the one being removed (its discoverer), so every removal is legal.
Related problems
Start free on Cariara · Coding problems · System design studio
