Most Stones Removed with Same Row or Column

Description

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

Solution(javascript)

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}
/**
 * @param {number[][]} stones
 * @return {number}
 */
const removeStones = function (stones) {
  const uf = new UnionFind(stones.length)
  for (let i = 0; i < stones.length; i++) {
    for (let j = i + 1; j < stones.length; j++) {
      const [x1, y1] = stones[i]
      const [x2, y2] = stones[j]
      if (x1 === x2 || y1 === y2) {
        uf.union(i, j)
      }
    }
  }
  const used = []
  let count = 0
  for (let i = 0; i < stones.length; i++) {
    const currentRoot = uf.root(i)
    if (!used[currentRoot]) {
      used[currentRoot] = true
      count += uf.size[currentRoot] - 1
    }
  }
  return count
}