947. Most Stones Removed with Same Row or Column

947

MediumUnion-Find / Disjoint Set UnionUnion-Find on rows and columnsConnected components, keep one per group

Most Stones Removed with Same Row or Column

On a 2D plane there are n stones, each at an integer coordinate with at most one stone per point. A stone can be removed if it shares its row or its column with another stone that has not yet been removed. Return the largest number of stones you can remove.

Open official problem prompt ↗

In plain English

Compute the maximum removable stones, which equals total stones minus the number of connected components formed by shared rows and columns.

Picture it like this

Picture threads tying stones that share a line. As long as a stone is still tied to a neighbor, you can lift it off. You can keep lifting until each cluster has just one anchor stone left.

Example

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Why: All six stones form one connected component through shared rows/columns, so you can remove all but one, leaving 6 - 1 = 5 removed.

Constraints

1 <= stones.length <= 10000 <= xi, yi <= 10^4No two stones are at the same coordinate point

Pattern lesson

See the pattern, then code

Connected components, keep one per group

↗

Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Within any connected component you can always remove stones down to a single survivor by peeling them off in reverse order of connection. So the maximum removed is n minus the number of connected components. Union each stone's row with its column to build those components.

New words, made simpleKnow these before the algorithm

Row/column node: We give each row and each column its own DSU element and connect a stone's row to its column.
Connected component: A maximal set of stones reachable through shared rows/columns.
Survivor: The single stone that must remain in each component after removals.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Repeated greedy removal

Simulates the process directly but is slow and easy to get wrong on ordering.

Repeatedly scan for a removable stone and delete it until none remain.

Time O(n^2) or worseSpace O(n)

Best choiceUnion-Find components

Reduces the whole problem to a component count.

Union row and column of each stone, count components, return n minus that.

Time O(n α(n))Space O(n)

The rule we keep true

Invariant

Two stones are in the same DSU component if and only if they are connected through a chain of shared rows and columns.

Why this is correct

Reasoning

Any connected component with k stones can be reduced to a single stone: remove stones in reverse order of a spanning tree so each removed stone still shares a line with a not-yet-removed one. Thus each component contributes exactly one non-removable stone, and the total removed is n minus the component count.

The algorithm in three movesSay these aloud before coding

1Model each row index and each column index as distinct DSU nodes

union(r0,c0), union(r0,c1) -> rows/cols link

2For every stone, union its row node with its column node

union(r1,c0) joins via c0

3Every stone now lies in one component via its row-column link

all stones share one root

4Count distinct roots among the stones; answer is n minus that count

components=1, answer=6-1=5

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

(0,0)0

(0,1)1

(1,0)2

(1,2)3

(2,1)4

(2,2)5

1 · Readr=0,c=0

2 · AskUnion row/col

3 · Update state{('r',0),('c',0)} joined

4 · Resultone set

Key takeaway

Row and column tags of the stones collapse into a single connected component.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Tagged nodes
Keys like ('r',0) and ('c',0) keep row and column namespaces separate so row 0 and column 0 are different nodes.
2
Lines 5-10find with lazy insert
setdefault registers a node the first time it is seen so we need not pre-populate.
3
Lines 15-16Link row to column
Each stone connects its row tag to its column tag, threading everything on those lines together.
4
Lines 18-19Count and subtract
Distinct roots over the stones' row tags gives the component count; n minus that is the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single stone: 0 components-worth to remove, answer 0
Stones all in one row (or one column) forming a single component
Two isolated stones sharing neither row nor column give answer 0

Common beginner mistakes

Using the same namespace for rows and columns so row 3 collides with column 3
Counting stones instead of distinct roots when computing components
Trying to simulate removals and mishandling the order, when component counting is exact

Check your understanding

Why can every connected component be reduced to exactly one remaining stone?

PyPython 3 · solution.py

Optimal

1class Solution:2    def removeStones(self, stones: list[list[int]]) -> int:3        parent: dict[tuple[str, int], tuple[str, int]] = {}45        def find(x):6            parent.setdefault(x, x)7            while parent[x] != x:8                parent[x] = parent[parent[x]]9                x = parent[x]10            return x1112        def union(a, b):13            parent[find(a)] = find(b)1415        for r, c in stones:16            union(('r', r), ('c', c))1718        roots = {find(('r', r)) for r, c in stones}19        return len(stones) - len(roots)

Time complexityO(n α(n))Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleUber

Most Stones Removed with Same Row or Column

Most Stones Removed with Same Row or Column

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Union-Find / Disjoint Set Union