947 Most Stones Removed with Same Row or Column

947. 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的数目。

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)