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 <= stones.length <= 1000
0 <= stones[i][j] < 10000

Solution

  1. number of island: dfs, calculate number of components, the result is the difference between number of stones and components
  2. union find find采用路径压缩

本质上,本题主要是求连通分量的个数,即可以用dfs和uf

Complexity

O(N) O(N)

Code

// dfs

class Solution {
    public int removeStones(int[][] stones) {
        Set<int[]> set = new HashSet<>();
        int numOfIsland = 0;
        for(int[] stone : stones){
            if(!set.contains(stone)){
                dfs(stone, stones, set);
                numOfIsland++;
            }
        }
        return stones.length - numOfIsland;        
    }
    public void dfs(int[] s1, int[][] stones, Set<int[]> visited){
        if(visited.contains(s1)) return;
        visited.add(s1);
        for(int[] s2 : stones){
            if(s1[0] == s2[0] || s1[1] == s2[1])
                dfs(s2, stones, visited);
        }
        
    }
}
// union find
class Solution {
    private int count = 0;
    public int removeStones(int[][] stones) {
        count = stones.length;
        int[] parent = new int[stones.length];
        for(int i = 0; i < parent.length; i++) parent[i] = i;
        
        for(int i = 0; i < stones.length; i++){
            for(int j = i + 1; j < stones.length; j++){
                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
                    union(parent, i, j, stones);
            }
        }
        return stones.length - count;
    }
    public void union(int[] parent, int i, int j, int[][] stones){
        int parent1 = find(parent, i);
        int parent2 = find(parent, j);
        
        if(parent1 == parent2) return;
        
        parent[parent2] = parent1;
        count--;
    }
    public int find(int[] parent, int i){
        if(parent[i] != i){
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }
}