DSA problem
Most Stones Removed with Same Row or Column
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the i-th stone, return the largest possible number of stones that can be removed.
The key insight is that two stones sharing a row or column are connected; the relation is transitive across chained stones. So we can group stones into connected components where any two stones in the same component share at least a chain of row/column equality. For each component of size k, we can remove exactly k - 1 stones (leave one survivor that anchors the others). Summed across all components, the answer is n - components.
To implement this efficiently, build a DSU not over stones but over rows and columns. Map each row r to id r and each column c to id c + 10001 (the offset is one more than the maximum row index, ensuring rows and columns never collide). For each stone (r, c), union its row id and column id. Two stones end up connected iff their rows/columns end up in the same DSU component.
Finally, count the number of unique roots among only those ids actually used by at least one stone. Subtract this from n and you have the answer. This runs in O(n * alpha(n)) and uses O(n) extra space — strictly better than the O(n^2) brute-force adjacency build.
Examples
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]5stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]3stones = [[0,0]]0Constraints
- 1 <= stones.length <= 1000
- 0 <= xi, yi <= 10^4
- No two stones are at the same coordinate point.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.