947. Most Stones Removed with Same Row or Column

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

Solutions:

  • Method 1: Union find
    • Union the row and col, it means if we have a stone, we union the row number and col number. 
      class Solution {
  private int[] uf;
  public int removeStones(int[][] stones) {
      this.uf = new int[20000];
      for(int i = 0; i < uf.length; i++) uf[i] = i;
      for(int[] stone : stones){
          union(stone[0], stone[1] + 10000);  // union the row with col
      }
      Set<Integer> seen = new HashSet<>();
      for(int[] stone : stones){
          seen.add(find(stone[0]));
      }
      return stones.length - seen.size();
  }
  private int find(int i){
      if(uf[i] != i){
          uf[i] = find(uf[i]);
      }
      return uf[i];
  }
  private void union(int i, int j){
      int p = find(i);
      int q = find(j);
      uf[p] = q;
  }
}
  • Method 2: dfs
    • Check all stones and if row number or col number is same, we can do the dfs. 
      class Solution {
  public int removeStones(int[][] stones) {
      Set<int[]> visited = new HashSet<>();
      int count = 0;
      for(int[] stone : stones){
          if(visited.contains(stone)) continue;
          dfs(stone, visited, stones);
          count++;
      }
      return stones.length - count;
  }
  private void dfs(int[] stone, Set<int[]> visited, int[][] stones){
      visited.add(stone);
      for(int[] s : stones){
          if(visited.contains(s)) continue;
          if(stone[0] == s[0] || stone[1] == s[1])
              dfs(s, visited, stones);
      }
  }
}