Most Stones Removed with Same Row or Column

Explanation & Solution

Description

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Output: 5

Explanation: One way to remove 5 stones is: remove (2,2) → (2,1) → (1,2) → (1,0) → (0,1). Only (0,0) remains.

Constraints

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

Approach

Union Find pattern

1. Map Rows and Columns as Union Find Nodes

Each row index r and column index c become separate nodes
To avoid collision between row 1 and column 1, use ~c (bitwise complement) for columns
This gives rows and columns distinct keys in the same Union Find

2. Union Row and Column for Each Stone

For each stone at [r, c], union r and ~c
This means all stones sharing a row or column end up in the same component transitively

3. Count Connected Components

Find the root of each stone's row and collect unique roots
The number of unique roots = number of connected components

4. Compute Answer

In each connected component of size k, we can remove k - 1 stones (leave one behind)
Total removable = total stones - number of components

Key Insight

Stones sharing a row or column form connected components — within each component all but one stone can be removed
Using row/column as Union Find nodes (instead of stone indices) naturally captures the sharing relationship

Time

**O(n · α(n))** where n is the number of stones

Space

O(n) for the Union Find maps

Solution Code

Satisfiability of Equality Equations

Smallest String with Swaps