# 947     Most Stones Removed with Same Row or Column

## 947. [Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/)

## 1. Question

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`

## 2. Implementation

**(1) Union Find**

思路: 题目给出石头所在的坐标，只要两个石头在同一行或者同一列，则可以将其中一个石头拿走，问最多可以拿走多少个石头。其实这里拿走石头其实就相当于将一个石头归并到另一个石头中，这很典型的union-find的题目，union的规则也很简单，只要两个石头在同一行或者同一列即可。最后最多能拿走的石头的数量等于原来石头数量减去union中cluster的数目。

```java
class Solution {
    public int removeStones(int[][] stones) {
        if (stones == null || stones.length == 0) {
            return 0;
        }

        int n = stones.length;

        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < stones.length - 1; i++) {
            for (int j = i + 1; j < stones.length; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    uf.union(i, j);
                }
            }
        }
        return n - uf.getCount();
    }

    class UnionFind {
        int[] root;
        int[] size;
        int count;

        public UnionFind (int n) {
            root = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                root[i] = i;
                size[i] = 1;
            }
        }


        public int find(int node) {
            while (node != root[node]) {
                node = root[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);

            if (rootI == rootJ) return;

            if (size[rootI] < size[rootJ]) {
                root[rootI] = root[rootJ];
                size[rootJ] += size[rootI];
            }
            else {
                root[rootJ] = root[rootI];
                size[rootI] += size[rootJ];
            }
            --count;
        }

        public int getCount() {
            return count;
        }
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n^2 \* logn), union-find的过程需要O(logn)，遍历输入数组，检查它们的行或列是否相同需要O(n^2)时间, 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/union-find/947-most-stones-removed-with-same-row-or-column.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.