947. Most Stones Removed with Same Row or Column

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

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

• Time : O(n)
• Space : O(n)

just focus on how many groups made

class Solution {
    unordered_map<int, int> group;
    int island = 0;
    int find(int n) {
        if(!group.count(n)) group[n] = n, island++; //if there is no island, add island
        if(n != group[n]) group[n] = find(group[n]);
        return group[n];
    }
    void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if(pa != pb) group[pa] = pb, island--; //merge two islands and remove 1
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        for(int i = 0; i < n; i ++) {
            merge(stones[i][0], ~stones[i][1]);
        }
        return n - island;
    }
};

• Time : O(n^2 logn)
• Space : O(n)

class Solution {
    int find(vector<int>& g, int n) {
        return g[n] == n ? n : g[n] = find(g, g[n]);
    }
    void merge(vector<int>& g, int a, int b) {
        int pa = find(g,a), pb = find(g,b);
        g[pa] = g[pb] = min(pa, pb);
    }
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        vector<int> group(n, 0);
        for(int i = 0; i < n; i++) group[i] = i;
        for(int i = 0; i < n; i ++) {
            for(int j = i + 1; j < n; j++) {
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    merge(group,i,j);
                }
            }
        }
        
        unordered_set<int> groupCount;
        for(int i = 0; i < n; i++) {
            groupCount.insert(find(group,i));
        }
        return n - groupCount.size();
    }
};