947. 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

Thoughts:

1. Union Find: Similar to number of islands, where a "connected" graph is a island. Unify the row and col index (Original Post)
   1. Optimization: Path Compression, Union by rank (see 305. Number of Islands II)
2. DFS: number of islands -> island: collection of points connected by row or column (Original Post)

Code: T: O(n) -> O(1)

class Solution {
public:
    unordered_map <int, int> f;
    int islands = 0;

    int removeStones(vector<vector<int>>& stones) {
        for(int i = 0; i < stones.size(); i++){
            unify(stones[i][0], ~stones[i][1]);
        }    
        return stones.size() - islands;
    }

    int find(int x){
        if (!f.count(x)) f[x] = x, islands++;
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    void unify(int x, int y){
        x = find(x), y = find(y);
        if (x != y) f[x] = y, islands--;
    }

};

Code: T:O(n) -> O(1): Path Compression + Union by rank

class Solution(object):
    def removeStones(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        UF = {}
        """
        Union by rank
        rank = {}
        """
        def find(x):
            while UF[x] != x:
                """
                Path Compression
                UF[x] = UF[UF[x]]
                """
                x = UF[x]
            return x

        def union(x,y):
            UF.setdefault(x, x);
            UF.setdefault(y, y);

            """
            Union by rank
            rank.setdefault(x, 0);
            rank.setdefault(y, 0);
            if rank[x] > rank[y]:
                x, y = y, x
            rank[y] += rank[x] == rank[y]
            """                
            UF[find(x)] = find(y) 


        for i, j in stones:
            union(i, ~j);

        cc = {find(x) for x in UF} # set
        return len(stones) - len(cc)

Code: DFS: discard points for the same island

class Solution:
    def removeStones(self, stones):
        def dfs(i, j):
            points.discard((i, j))
            for y in rows[i]:
                if (i, y) in points:
                    dfs(i, y)
            for x in cols[j]:
                if (x, j) in points:
                    dfs(x, j)
        points, island, rows, cols = {(i, j) for i, j in stones}, 0, collections.defaultdict(list), collections.defaultdict(list)
        for i, j in stones:
            rows[i].append(j)
            cols[j].append(i)
        for i, j in stones:
            if (i, j) in points:
                dfs(i, j)
                island += 1
        return len(stones) - island