Most Stones Removed with Same Row or Column medium
Description
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.
Return the largest possible number of stones that can be removed.
Examples
> Case 1:
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
> Case 2:
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
> Case 3:
stones = [[0,0]]
Output: 0Constraints
1 <= stones.length <= 10000 <= xi, yi <= 10^4- No two stones are at the same coordinate point.
State design / Intuition
Key insight: All stones in the same connected component can be reduced to exactly one (the last remaining stone). So the answer is n − (number of connected components).
Two stones are “connected” if they share a row or column. Transitivity means if A shares a row with B, and B shares a column with C, then A, B, C are in the same component — even if A and C share nothing.
Union-Find trick: Union stones by row and column. We can treat rows and columns as nodes in the union-find. A stone at (r, c) connects row r to column c. To avoid index collision between rows and columns, offset columns by a fixed amount (e.g., col + 10001).
Code
The + 10001 offset maps column indices into a disjoint range from row indices (rows: 0–10000, cols: 10001–20001). Without this, row 5 and column 5 would be treated as the same node, merging unrelated stones. The offset ensures a stone at (5, 3) correctly merges row 5 with column 3 (represented as 10004) rather than rows 5 and 3.
Analysis
- Time: O(n α(max_coord)) ≈ O(n).
- Space: O(n + max_coord) for the hash map.
Alternative using an array instead of a map if max coordinate is bounded.
Same skin
- Accounts Merge — union-find on email strings; same “group by shared attribute” pattern.
- Number of Islands II — dynamic union-find as stones are added one by one.
- Largest Component Size by Common Factor — union-find grouping numbers by shared prime factor.
- Satisfiability of Equality Equations — union-find with constraint validation.