Pattern visualizer

Maximum Stone Removal

A stone can be removed as long as some other stone still shares its row or column. That means inside any connected cluster of stones you can always keep removing until exactly one is left — never zero, because the last removal needs a partner. So the answer is not about WHICH stones to remove, only about how many separate clusters exist: total stones minus the number of clusters. Union-find tracks that count directly — union a stone with the first stone already seen in its row, and separately with the first stone already seen in its column — with no need to ever look at pairs of stones that don't share one. Animated on: 6 stones at (0,0), (0,1), (1,0), (1,2), (2,1), (2,2) — two stones are connected if they share a row or a column. What is the maximum number of stones that can be removed?.

Union-find: stones sharing a row or column collapse into one survivor

time O(N * α(N))space O(N)step 1 / 9

Edge = same row or same column

(0,0)

(0,1)

(1,0)

(1,2)

(2,1)

(2,2)

line 1

6 stones. Treat each stone as a graph node and draw an edge between two stones that share a row or a column — a whole connected cluster can always be trimmed down to exactly ONE surviving stone, so the answer is just stones minus the number of clusters.

Pseudocode

1FUNCTION removeStones(stones):
2  FOR i FROM 0 TO LENGTH(stones) - 1
3    (r, c) <- stones[i]
4    IF rowFirst[r] EXISTS
5      UNION(i, rowFirst[r])
6    ELSE
7      rowFirst[r] <- i
8    IF colFirst[c] EXISTS
9      UNION(i, colFirst[c])
10    ELSE
11      colFirst[c] <- i
12  roots <- SET OF FIND(i) FOR EACH i
13  RETURN LENGTH(stones) - SIZE(roots)

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap