Most Stones Removed with Same Row or Column

Bipartite row/column union-find: stones - connected components

time O(N * a(N))space O(N)

Never simulate the removals. Treat every row index and every column index as its own node, and let each stone be one edge joining its row-node to its column-node — two stones can always be chained down to one survivor exactly when their nodes sit in the same connected piece. A union-find over those row/column nodes finds every piece in one pass over the stones, and a piece of k stones always yields k - 1 removable ones, so the answer is simply the stone count minus the number of pieces.

Details

Animated on: 6 stones at (0,0), (0,1), (1,0), (1,2), (2,1), (2,2) — a stone can be removed only while another stone still shares its row or column. What is the maximum number removable?

Problem:Most Stones Removed with Same Row or ColumnMedium

Bipartite row/column union-find: stones - connected components

step 1 / 9

One node per row, one per column

6 stones sit on 3 rows and 3 columns. Instead of graphing stone-to-stone, make each row and each column its own node: stone (r, c) becomes one edge between row r and column c. Two stones end up removable together exactly when their nodes land in the same connected piece.

Pseudocode

1FUNCTION removeStones(stones):
2  FOR EACH [r, c] IN stones
3    UNION(ROW(r), COL(c))
4  roots <- EMPTY SET
5  FOR EACH [r, c] IN stones
6    ADD FIND(ROW(r)) TO roots
7  RETURN LENGTH(stones) - SIZE(roots)

← / → step · space play · Home restart

Every step in words

Show all 9 steps

6 stones sit on 3 rows and 3 columns. Instead of graphing stone-to-stone, make each row and each column its own node: stone (r, c) becomes one edge between row r and column c. Two stones end up removable together exactly when their nodes land in the same connected piece.
Stone (0, 0) links R0 to C0. R0 rooted at R0, C0 rooted at C0 — different pieces, so merge them. That drops the component count to 5.
Stone (0, 1) links R0 to C1. R0 rooted at C0, C1 rooted at C1 — different pieces, so merge them. That drops the component count to 4.
Stone (1, 0) links R1 to C0. R1 rooted at R1, C0 rooted at C1 — different pieces, so merge them. That drops the component count to 3.
Stone (1, 2) links R1 to C2. R1 rooted at C1, C2 rooted at C2 — different pieces, so merge them. That drops the component count to 2.
Stone (2, 1) links R2 to C1. R2 rooted at R2, C1 rooted at C2 — different pieces, so merge them. That drops the component count to 1.
Stone (2, 2) links R2 to C2. Both already root at C2 — this stone just adds a second connection inside a group we already have, so the component count stays 1.
Re-check every stone's row node after all the merging: they all resolve to root C2. Only 1 connected piece remain among the 6 stones.
Each connected piece of k stones can be whittled down to 1 stone by removing leaves one at a time, so it always contributes k - 1 removable stones. Summed over every piece that is just 6 total stones minus 1 piece, which is 5. RETURN 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Most Stones Removed with Same Row or Column in the editor All Graph problems Back to roadmap