Most stones removed with same row or column

Medium

Each component leaves one stone behind

Problem

Given stones on a grid, remove as many as possible where each removed stone shares a row or column with another. Return the max removed.

In simple words

Union stones sharing a row or column; each connected group can shrink to one stone.

The idea

Stones sharing a row or column are connected, and within any connected component you can remove every stone but one. So the answer is the total number of stones minus the number of components.

The trick

Union stones by row and by column indices.
Offset the column identifiers so they cannot collide with row identifiers.
Answer = stones - components.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output:: 5
Explanation:: All connect into one group → remove 5.

Example 2

Input:: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output:: 3
Explanation:: Remove 3, leaving 2 groups.

Example 3

Input:: stones = [[0,0]]
Output:: 0
Explanation:: A lonely stone can't be removed → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.