> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/most-stones-removed-with-same-row-or-column.md).

# Most Stones Removed with Same Row or Column

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

Now, a *move* consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

**Example 1:**

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

**Example 2:**

```
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
```

**Example 3:**

```
Input: stones = [[0,0]]
Output: 0
```

**Note:**

1. `1 <= stones.length <= 1000`
2. `0 <= stones[i][j] < 10000`

```java
class Solution {
    public int removeStones(int[][] stones) {
        int[] parent = new int[20000];
        for (int i = 0; i < 20000; ++i)
            parent[i] = i;
        int N = stones.length;
        // build unions
        for (int[] stone : stones) {
            union(stone[0], stone[1] + 10000, parent);
        }
        Set<Integer> seen = new HashSet();
        for (int[] stone : stones) {
            // One component has one top parent
            seen.add(find(stone[0], parent));
        }
        // Now we can remove everything except one stone from each component
        return N - seen.size();

    }

    public int find(int x, int[] parent) {
        if (parent[x] != x)
            parent[x] = find(parent[x], parent);
        return parent[x];
    }

    public void union(int x, int y, int[] parent) {
        parent[find(x, parent)] = find(y, parent);
    }
}
```