Most Stones Removed with Same Row or Column
Problem Statement
You are given n stones on a 2D grid. Each stone has integer coordinates [row, col], and no two stones share the same coordinate.
You may remove a stone if there is another stone still remaining in the same row or the same column. Return the maximum number of stones you can remove.
Input
An array stones where each entry is a row and column coordinate.
Output
An integer: the maximum number of stones that can be removed while following the row or column rule.
Constraints
- •
1 <= stones.length <= 1000 - •
0 <= row, col <= 10000 - •
No two stones have the same coordinate
Examples
Example 1
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
5Example 2
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
3Learning Objectives
- Convert a removal process into a connected-components counting problem.
- Use DSU over rows and columns as separate node types instead of comparing every pair of stones.
- Prove the formula **answer = stones - components** for this class of problems.
Intuition
A stone is removable as long as it is not the last stone in its connected cluster. In a cluster where stones are linked by shared rows or columns, you can always keep one stone as the anchor and remove the rest. Therefore a component with k stones contributes k - 1 removals, and summing over components gives n - number of components.
The trick is how to build components efficiently. Instead of creating an edge between every pair of stones in the same row or column, create nodes for rows and nodes for columns. A stone at (r, c) connects row r to column c. If two stones share a row, they touch the same row node; if they share a column, they touch the same column node. Unioning row nodes with column nodes captures the same connectivity with one union per stone.
Because row ids and column ids live in different namespaces, shift columns by an offset such as 10001. Then row 5 and column 5 do not collide.
Common mistakes
- ×Counting roots for every possible row and column id. Only roots touched by actual stones matter.
- ×Forgetting to offset columns, causing row 7 and column 7 to be treated as the same node.
- ×Returning the number of components instead of **n - components**.
- ×Pairwise comparing all stones by row and column. That works for small inputs but misses the intended DSU pattern.
- ×Thinking each component must have a cycle. A tree-shaped connected component of stones can still be reduced to one remaining stone.
Algorithm Explanation
- Allocate a Union-Find for row ids 0..10000 and column ids 10001..20001.
- For each stone [r, c], union r with c + 10001. This joins every stone that shares a row or column into the same connected component.
- After all unions, create a set of roots by calling find on each stone's row id. Each stone contributes one touched root, and equal roots mean the stones belong to the same component.
- Return stones.length - rootCount.
Solutions
Solution: Union-Find over row and column nodes
Use this when grid coordinates define relationships but the grid itself is sparse. DSU avoids building a huge matrix or comparing every pair of stones.
Represent each row and each column as a DSU node. A stone connects its row node to its shifted column node. Connected components among touched nodes correspond exactly to connected components among stones.
Step-by-step
- Choose OFFSET = 10001 because rows and columns are at most 10000.
- Union row with col + OFFSET for every stone.
- Count distinct roots among the row ids of the stones. Counting row ids is enough because every stone's row and column have already been unioned.
- Subtract the component count from the number of stones.
O(n · α(C))
O(C)
C is the fixed coordinate universe of 20002 row and shifted-column nodes. With coordinate compression, space becomes O(n).
Java implementation
Dry Run
Sample input
stones = [[0,0],[0,1],[1,0],[2,2]]. Columns are shifted by 10001, so column 0 is node 10001.
| Step | Stone | Union | Components among stones | Formula |
|---|---|---|---|---|
| 1 | [0,0] | union row 0 with col 10001 | {[0,0]} | 4 - ? |
| 2 | [0,1] | union row 0 with col 10002 | {[0,0],[0,1]} | same row connects them |
| 3 | [1,0] | union row 1 with col 10001 | {[0,0],[0,1],[1,0]} | same column joins row 1 |
| 4 | [2,2] | union row 2 with col 10003 | plus isolated {[2,2]} | two components total |
| 5 | Count roots | roots for rows 0,0,1 are same; row 2 differs | 2 components | 4 - 2 = 2 |
The first three stones form one connected component through row 0 and column 0. The last stone has no shared row or column, so it is the second component. Each component must leave one stone behind, so the maximum removals are 4 - 2 = 2.
Interview Tips
State the invariant before writing code: in each connected component, all but one stone can be removed, so the answer is n - components. Then explain the row-column DSU trick. This is the part interviewers are looking for: a stone is an edge between a row node and a column node, not just a point in a matrix.
Likely follow-ups
- What if row and column coordinates are up to one billion? Coordinate-compress rows and shifted columns with a HashMap instead of allocating a fixed array.
- Return one valid removal order. Build component memberships and repeatedly remove a stone that still shares a row or column inside its component.
- How would the answer change if diagonal sharing also allowed removal? Add diagonal families as additional node types.
- Can you solve it with DFS? Yes, build a graph of stones connected by shared row or column, but DSU is cleaner for sparse coordinates.
Similar Problems
Key Takeaways
- Maximum removable stones equals total stones minus connected components.
- Rows and columns are separate node types; offset one namespace to avoid collisions.
- A stone can be viewed as an edge connecting its row node to its column node.
- Count roots only among nodes touched by stones, not the entire coordinate universe.