Problem Statement

There are n stones at integer coordinate points on a 2D plane, with at most one stone per coordinate point. Some stones need to be removed. A stone can be removed if it shares the same row or the same column as another stone that has not been removed.

Given an array of stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the maximum possible number of stones that can be removed.

Examples

Example 1:

Input: n = 6, stones = [
                        [0, 0],
                        [0, 1],
                        [1, 0],
                        [1, 2],
                        [2, 1],
                        [2, 2]
                       ]
Output: 5

Explanation: One of the many ways to remove 5 stones is to remove the following stones:
[0, 0]
[1, 0]
[0, 1]
[2, 1]
[1, 2]

Example 2:

Input: n = 6, stones = [
                        [0, 0],
                        [0, 2],
                        [1, 3],
                        [3, 1],
                        [3, 2],
                        [4, 3]
                       ]
Output: 4

Explanation: We can remove the following stones:
[0, 0]
[0, 2]
[1, 3]
[3, 1]

Different Approaches

1️⃣ Disjoint Set Data Structure

Observation:

Here, there are two different groups of stones possible (assuming 0-based indexing):

• The first group includes the stones at [0, 0], [0, 2], [3, 2], and [3, 1].
• The second group includes stones at [1, 3] and [4, 3].

Note that each group consists of all stones that share either a row or column with another stone in the same group. For a particular group, all the stones can be removed from the group except one (as there will be no stones sharing a row or column for the last stone).

How to identify the maximum number of nodes that can be removed?

Let's assume there are n stones in total. And these n stones have formed k different components each containing Xi no. of stones. This indicates the following:

Thus, the maximum number of stones that can be removed can be found if the number of connected components(k) in the graph is known.

How to get the number of connected components?

One way to find the number of connected components is by traversing the graph using one of the two traversal techniques.
Another way is to use the Disjoint Set data structure, which will help in connecting the stones that belong to the same group(component).

How to connect the cells containing stones to form a component?

To connect the cells it can be assumed that each entire row and column of the 2D plane is a particular node. Now, each row can be connected(united) with the corresponding column where the stones are located. However, the column number may be the same as the row number.
To avoid this, each column number can be converted to (column no. + total no. of rows) and the union of row number and the converted column number i.e. (column no. + total no. of rows) can be performed as shown in the following example:

For the above example, to connect the two stones in the cells [0, 0] and [0, 2] of the first row, firstly row number can be taken i.e. 0(because of 0-based indexing) as a node, and then the converted column numbers 0 to (0+5) and 2 to (2+5). Then, the union of (0 and 5) and (0 and 7) can be performed to form the connected components.

Approach:

1. Traverse the list of stones to find the maximum row and column indices. This helps in defining the size of the Disjoint Set data structure.
2. Create a Disjoint Set data structure large enough to accommodate all rows and columns. Each row and column is treated as a separate node.
3. For each stone, treat its row and column as nodes and unite them using the union by size method. This ensures that stones sharing the same row or column are in the same connected component.
4. Use a map to keep track of unique nodes that have stones. This helps in counting distinct connected components.
5. Iterate through the unique nodes and count how many distinct components there are by finding the ultimate parent of each node.
6. The maximum number of stones that can be removed is the total number of stones minus the number of connected components.
7. Return the calculated number of stones that can be removed.

Code:

#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
public:
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    vector<int> rank, parent, size;

    // Constructor
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // Function to find ultimate parent
    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }
    
    // Function to implement union by rank
    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
    
    // Function to implement union by size
    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

// Solution class
class Solution{
public:

    // Function to remove maximum stones 
    int maxRemove(vector<vector<int>>& stones, int n) {
        
        /* To store the maximum row 
        and column having a stone */
        int maxRow = 0;
        int maxCol = 0;
        
        // Iterate on all the nodes
        for (auto it : stones) {
            maxRow = max(maxRow, it[0]);
            maxCol = max(maxCol, it[1]);
        }
        
        // Disjoint Set data structure
        DisjointSet ds(maxRow + maxCol + 1);
        
        // To store the nodes having a stone in Disjoint Set
        unordered_map<int, int> stoneNodes;
        
        // Iterate on all stones
        for (auto it : stones) {
            
            // Row number
            int nodeRow = it[0];
            
            // Converted column number
            int nodeCol = it[1] + maxRow + 1;
            
            // United two nodes
            ds.unionBySize(nodeRow, nodeCol);
            
            // Add the nodes to the map
            stoneNodes[nodeRow] = 1;
            stoneNodes[nodeCol] = 1;
        }
        
        // To store the number of connected components
        int k = 0;
        
        // Iterate on the set
        for (auto it : stoneNodes) {
            
            /* Increment the count if 
            a new component is found */
            if (ds.findUPar(it.first) == it.first) {
                k++;
            }
        }
        
        // Return the answer
        return n - k;
    }
};


int main() {
    int n = 6;
    vector<vector<int>> stones = {
        {0, 0}, {0, 1}, {1, 0},
        {1, 2}, {2, 1}, {2, 2}
    };

    // Creating instance of Solution class
    Solution sol;
    
    /* Function call to get the 
    size of the largest island */
    int ans = sol.maxRemove(stones, n);
    
    // Output
    cout << "The size of the largest island is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) The given stones array is traversed multiple times. Traversing the hashset will also take O(N) time.
• Space Complexity:O(Max Row number + Max Column number).
  • The Disjoint set will store the nodes using the parent and size/rank array which will take (2*number of nodes) space. Since, the number of nodes = max row number + max column number, the overall space complexity is O(Max Row number + Max Column number).