Problem 25.4 · Union-Find (DSU)Medium

Most Stones Removed with Same Row or Column

What it teaches: Union a row with a column: stones link them, and each connected group can be reduced to one stone.

Practise it on judges as “Most Stones Removed with Same Row or Column”.

The problem

Stones sit on integer points. A stone can be removed if another remaining stone shares its row or column. Return the maximum number of stones that can be removed.

Example 1

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

Constraints

1 ≤ stones ≤ 1000
0 ≤ x, y ≤ 10⁴

Pattern clues in the wording

→ Shared row or column connects things
→ Answer = items − groups

These clues point to Union-Find: Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int removeStones(int[][] stones) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]	5
2	stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]	3
3	stones = [[0,0]]	0

From slow to fast

Approaches

1. Union rows with columns · O(n α(n))

Union rows with columns

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

For stone (x, y), union x with y + 10001 (so columns don't clash with rows). Count distinct roots among the used row/column nodes. Answer = stones − groups.

Approach 1

import java.util.*;

class Solution {
    private final int[] parent = new int[20002];

    public int removeStones(int[][] stones) {
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int[] s : stones) parent[find(s[0])] = find(s[1] + 10001);
        Set<Integer> roots = new HashSet<>();
        for (int[] s : stones) roots.add(find(s[0]));
        return stones.length - roots.size();
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Avoids comparing every pair of stones.

Before you submit

Edge cases and common mistakes

Test these inputs

One stone (0)
No two stones share a line

Mistakes people make

Using the same id space for rows and columns (row 3 and column 3 would merge).

Interview

Follow-up questions

Why can all but one stone in a group be removed?

Command Palette

The problem

Approaches

Union rows with columns

Edge cases and common mistakes

Follow-up questions