947. Most Stones Removed With Same Row Or Column

/**

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

 * Example 1:

 * Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

 * Output: 5

 * Explanation: One way to remove 5 stones is as follows:

 * 1. Remove stone [2,2] because it shares the same row as [2,1].

 * 2. Remove stone [2,1] because it shares the same column as [0,1].

 * 3. Remove stone [1,2] because it shares the same row as [1,0].

 * 4. Remove stone [1,0] because it shares the same column as [0,0].

 * 5. Remove stone [0,1] because it shares the same row as [0,0].

 * Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.

 * Example 2:

 * Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

 * Output: 3

 * Explanation: One way to make 3 moves is as follows:

 * 1. Remove stone [2,2] because it shares the same row as [2,0].

 * 2. Remove stone [2,0] because it shares the same column as [0,0].

 * 3. Remove stone [0,2] because it shares the same row as [0,0].

 * Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

 * Example 3:

 * Input: stones = [[0,0]]

 * Output: 0

 * Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

 * /

See the solution on github here:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/graph/StonesRemoved.java

The solution will use union find (disjoint sets) to solve the problem. See the union find algorithm on wiki pedia here: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

See my code on union find at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/utils/graph/generic/UnionFindNode.java

The algorithm is:

1. Iterate through the stones while connecting the stones on the same row and those on the same column via union/find – union operation
   1. We add (2000) to the column value so as to make them distinct from the row value
2. We iterate through the stones via creating a unique parent set via calling the find method on each union find node.
3. The number of parent nodes returned in 2 identify the unique groups of connected stones.
4. We can calculate the stones removed via subtracting total stones from the # in 3 (stones left).

Here is the code:

public int removeStones(int[][] stones) {
    Map<Integer, UnionFindNode<Integer>> unionFindMap = new HashMap<>();
    for (int i = 0; i < stones.length; i++) {
        UnionFindNode<Integer> unionA = new UnionFindNode<>(stones[i][0]);
        //adding 20000 to cols , so columns and rows have diff ids
        UnionFindNode<Integer> unionB = new UnionFindNode<>(stones[i][1] + 20000);
        unionFindMap.put(stones[i][0], unionA);
        unionFindMap.put(stones[i][1] + 20000, unionB);
        unionA.union(unionB);
    }
    Set<Integer> parentsSet = new HashSet<>();
    for (int i = 0; i < stones.length; i++) {
        UnionFindNode<Integer> unionA = unionFindMap.get(stones[i][0]);
        parentsSet.add(unionA.find().getValue());
    }
    return stones.length - parentsSet.size();
}