Intuition

The problem can be viewed as finding the number of connected components in a graph where each stone represents a node, and edges exist between nodes (stones) that share the same row or column. The goal is to maximize the number of stones that can be removed while keeping at least one stone in each connected component. Using the Union-Find data structure can efficiently manage the merging of nodes into components.

Approach

The solution involves the following steps: 1. Initialize a Union-Find structure to manage the connected components. 2. Iterate through the list of stones, and for each stone, check if there's another stone in the same row or column. If so, union the two stones together. 3. After processing all stones, count the number of unique components. The result will be the total number of stones minus the number of components, as each component can have all but one stone removed.

Complexity

• Time complexity:
  The time complexity is $O(N \log^* N)$, where N is the number of stones. This is due to the near-constant time complexity of the Union-Find operations with path compression and union by rank.

• Space complexity:
  The space complexity is $O(N)$, where N is the number of stones. This is due to the storage required for the Union-Find parent, rank, and size arrays, as well as the hash maps used to store row and column mappings.

Code

```java class Solution { public int removeStones(int[][] stones) { int N = stones.length; UnionFind stoneUnion = new UnionFind(N); Map X_map = new HashMap<>(); Map Y_map = new HashMap<>();

    for (int i = 0; i < N; i++) {
        int x = stones[i][0];
        int y = stones[i][1];

        if (X_map.containsKey(x)) {
            stoneUnion.union(i, X_map.get(x));
        } else {
            X_map.put(x, i);
        }

        if (Y_map.containsKey(y)) {
            stoneUnion.union(i, Y_map.get(y));
        } else {
            Y_map.put(y, i);
        }
    }

    int uniqueComponents = 0;
    for (int i = 0; i < N; i++) {
        if (stoneUnion.find(i) == i) {
            uniqueComponents++;
        }
    }

    return N - uniqueComponents;
}

}

class UnionFind { private final int[] parents; private final int[] rank; private final int[] size;

public UnionFind(int size) {
    parents = new int[size];
    rank = new int[size];
    this.size = new int[size];
    for (int i = 0; i < size; i++) {
        parents[i] = i;
        rank[i] = 1;
        this.size[i] = 1;
    }
}

public int find(int node) {
    if (parents[node] != node) {
        parents[node] = find(parents[node]); // Path compression
    }
    return parents[node];
}

public void union(int nodeX, int nodeY) {
    int rootX = find(nodeX);
    int rootY = find(nodeY);

    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parents[rootY] = rootX;
            size[rootX] += size[rootY];
        } else if (rank[rootX] < rank[rootY]) {
            parents[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parents[rootY] = rootX;
            rank[rootX]++;
            size[rootX] += size[rootY];
        }
    }
}

}