Most stones removed with same row or column

Intuition:

Observation:

Consider the following example:

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

If the stones are considered as nodes, the different groups will refer to the different components of the graph.

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:

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.
Create a Disjoint Set data structure large enough to accommodate all rows and columns. Each row and column is treated as a separate node.
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.
Use a map to keep track of unique nodes that have stones. This helps in counting distinct connected components.
Iterate through the unique nodes and count how many distinct components there are by finding the ultimate parent of each node.
The maximum number of stones that can be removed is the total number of stones minus the number of connected components.
Return the calculated number of stones that can be removed.

Dry Run:

Solution:

#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;
}
import java.util.*;

class DisjointSet {
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    int[] rank, parent, size;

    // Constructor
    DisjointSet(int n) {
        rank = new int[n + 1];
        parent = new int[n + 1];
        size = new int[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 {
    // Function to remove maximum stones
    public int maxRemove(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 (int[] stone : stones) {
            maxRow = Math.max(maxRow, stone[0]);
            maxCol = Math.max(maxCol, stone[1]);
        }

        // Disjoint Set data structure
        DisjointSet ds = 
            new DisjointSet(maxRow + maxCol + 1);

        // To store the nodes having a stone in Disjoint Set
        Map<Integer, Integer> stoneNodes = new HashMap<>();

        // Iterate on all stones
        for (int[] stone : stones) {
            // Row number
            int nodeRow = stone[0];

            // Converted column number
            int nodeCol = stone[1] + maxRow + 1;

            // United two nodes
            ds.unionBySize(nodeRow, nodeCol);

            // Add the nodes to the map
            stoneNodes.put(nodeRow, 1);
            stoneNodes.put(nodeCol, 1);
        }

        // To store the number of connected components
        int k = 0;

        // Iterate on the set
        for (int key : stoneNodes.keySet()) {
            /* Increment the count if 
            a new component is found */
            if (ds.findUPar(key) == key) {
                k++;
            }
        }

        // Return the answer
        return n - k;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] stones = {
            {0, 0}, {0, 1}, {1, 0},
            {1, 2}, {2, 1}, {2, 2}
        };

        // Creating instance of Solution class
        Solution sol = new Solution();

        /* Function call to get the 
        size of the largest island */
        int ans = sol.maxRemove(stones, n);

        // Output
        System.out.println("The size of the largest island is: " + ans);
    }
}
class DisjointSet:
    # To store the ranks, parents and 
    # sizes of different set of vertices
    def __init__(self, n):
        self.rank = [0] * (n + 1)
        self.parent = [i for i in range(n + 1)]
        self.size = [1] * (n + 1)
    
    # Function to find ultimate parent
    def findUPar(self, node):
        if node == self.parent[node]:
            return node
        self.parent[node] = self.findUPar(self.parent[node])
        return self.parent[node]
    
    # Function to implement union by rank
    def unionByRank(self, u, v):
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v:
            return
        if self.rank[ulp_u] < self.rank[ulp_v]:
            self.parent[ulp_u] = ulp_v
        elif self.rank[ulp_v] < self.rank[ulp_u]:
            self.parent[ulp_v] = ulp_u
        else:
            self.parent[ulp_v] = ulp_u
            self.rank[ulp_u] += 1
    
    # Function to implement union by size
    def unionBySize(self, u, v):
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v:
            return
        if self.size[ulp_u] < self.size[ulp_v]:
            self.parent[ulp_u] = ulp_v
            self.size[ulp_v] += self.size[ulp_u]
        else:
            self.parent[ulp_v] = ulp_u
            self.size[ulp_u] += self.size[ulp_v]

# Solution class
class Solution:
    # Function to remove maximum stones 
    def maxRemove(self, stones, n):
        # To store the maximum row and column having a stone
        maxRow = 0
        maxCol = 0
        
        # Iterate on all the nodes
        for it in stones:
            maxRow = max(maxRow, it[0])
            maxCol = max(maxCol, it[1])
        
        # Disjoint Set data structure
        ds = DisjointSet(maxRow + maxCol + 1)
        
        # To store the nodes having a stone in Disjoint Set
        stoneNodes = {}
        
        # Iterate on all stones
        for it in stones:
            # Row number
            nodeRow = it[0]
            
            # Converted column number
            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
        k = 0
        
        # Iterate on the set
        for key in stoneNodes:
            # Increment the count if a new component is found
            if ds.findUPar(key) == key:
                k += 1
        
        # Return the answer
        return n - k

# Main function to test the Solution class
if __name__ == "__main__":
    n = 6
    stones = [
        [0, 0], [0, 1], [1, 0],
        [1, 2], [2, 1], [2, 2]
    ]

    # Creating instance of Solution class
    sol = Solution()
    
    # Function call to get the size of the largest island
    ans = sol.maxRemove(stones, n)
    
    # Output
    print("The size of the largest island is:", ans)
class DisjointSet {
    // Constructor
    constructor(n) {
        /* To store the ranks, parents and sizes 
        of different set of vertices */
        this.rank = new Array(n + 1).fill(0);
        this.parent = new Array(n + 1).fill(0).map((_, i) => i);
        this.size = new Array(n + 1).fill(1);
    }

    // Function to find ultimate parent
    findUPar(node) {
        if (node === this.parent[node]) return node;
        this.parent[node] = this.findUPar(this.parent[node]);
        return this.parent[node];
    }

    // Function to implement union by rank
    unionByRank(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.rank[ulp_u] < this.rank[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
        } else if (this.rank[ulp_v] < this.rank[ulp_u]) {
            this.parent[ulp_v] = ulp_u;
        } else {
            this.parent[ulp_v] = ulp_u;
            this.rank[ulp_u]++;
        }
    }

    // Function to implement union by size
    unionBySize(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v) return;
        if (this.size[ulp_u] < this.size[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
            this.size[ulp_v] += this.size[ulp_u];
        } else {
            this.parent[ulp_v] = ulp_u;
            this.size[ulp_u] += this.size[ulp_v];
        }
    }
}

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

// Main function to test the Solution class
(function main() {
    const n = 6;
    const stones = [
        [0, 0], [0, 1], [1, 0],
        [1, 2], [2, 1], [2, 2]
    ];

    // Creating instance of Solution class
    const sol = new Solution();
    
    // Function call to get the size of the largest island
    const ans = sol.maxRemove(stones, n);
    
    // Output
    console.log("The size of the largest island is: " + ans);
})();

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

Problem List

Most stones removed with same row or column

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Observation:

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

How to get the number of connected components?

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

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code