Most Stones Removed with Same Row or Column

On a 2D plane, stones[i] = [r, c] places a stone at row r, column c. A stone can be removed if it shares its row or column with another stone still on the plane. Return the maximum number of stones you can remove.

Hints

· Stuck? Reveal one nudge at a time.

Stones sharing a row or column are connected, and this relation is transitive.

From a component of k stones you can remove k-1, leaving one.

So the answer is (number of stones) - (number of connected components).

Common doubts

As long as a component has more than one stone, some stone shares a line with another and can be removed; peel until one remains.

Mapping each row and column to its first stone lets you union new stones with existing ones directly, no explicit edges.

You union stones that share a row OR a column, so you key by row and by column separately.

Interview follow-ups

· What an interviewer asks next.

Yes — treat 'row r' and 'col c' as nodes and union them per stone; components of the stones follow.

Add a diagonal key; the component structure changes accordingly.

Fun facts

LeetCode 947 — a components problem where the answer is n minus the component count.
The row/column first-owner trick is a compact way to union by a shared attribute.

Asked at

AmazonGoogleFacebook

Frequently Sometimes Occasionally

Example 1

Input: stones = [[0,0],[0,1],[1,0],[1,1]]
Output: 3
All four are connected via shared rows/columns — one component, so remove 3.

Example 2

Input: stones = [[0,0],[1,1],[2,2]]
Output: 0
No two share a row or column; each is isolated.

Constraints

- 0 <= stones.length <= 1000 - 0 <= r, c <= 10^4 - no two stones at the same coordinate

Two stones in the same row or column are connected, and connectivity is transitive — so the stones split into connected components. Within a component of k stones, you can always remove k-1 of them (remove them in an order that keeps a shared partner until the end, leaving exactly one). So the answer is simply:

max removed = (total stones) - (number of connected components).

Build the components by connecting stones that share a row or column. Union-Find does it slickly: keep a row → first stone and column → first stone map, and union each new stone with the first stone that already occupies its row and its column. Then the answer is n - #roots. O(n·α).

Prerequisites

Before you start

· Concepts used directly in the solution.

Same row/col = edge. connectivity is transitive.

Keep one per component. remove k-1 of k.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What makes a stone removable?”

Sharing a row or column with another remaining stone.

“How many remain?”

One per connected component.

The ideal opening — say it like this

Stones sharing a row or column form components; I can remove all but one from each.

So the answer is total stones minus the number of components — I count those with union-find.

Understand the problem

Worked example — stones = [[0,0],[0,1],[1,0],[1,1]]

all four share rows/columns -> one component of 4
removable = 4 - 1 = 3

Key observations

1Aha

Same row/col connects stones

Components form under this relation.

2Aha

Keep one per component

Remove size - 1 from each.

3Aha

Answer = n - components

Sum of (size - 1) over components.

Brute force vs optimal

	DFS on stone graph	Union-Find
Connect via	group by row/col, build edges	row/col first-owner maps
Time	O(n + edges)	O(n·α)
Answer	n - components	n - roots

Both count the same components. Full code is in the Approaches selector below.

Summary

Key takeaway

Stones sharing a row or column form components; you can remove all but one from each, so the answer is n minus the number of components. Union-find via row/column first-owner maps computes it in O(n·α).

union each stone with the first stone in its row and its column
answer = n - number of distinct roots