# Solution For Most Stones Removed With Same Row Or Column

The problem statement for the “Most Stones Removed With Same Row Or Column” problem on LeetCode is as follows:

You are given a 2D plane of stones, represented by a 2D array. Each element in the array is a pair of integers (i,j) representing the location of a stone at position (i,j). You want to remove as many stones as possible. The only restriction is that you cannot remove a stone if it shares a row or column with another stone that has not been removed.

Write a function to return the maximum number of stones you can remove.

To solve this problem, we can use the concept of disjoint sets.

We define a set for each stone where the set contains all the stones that are in the same row or column as that stone. We can use a dictionary to map each stone to its corresponding set.

We traverse through the stones one by one and if we find a stone (i,j) such that there is already a stone in the same row or column as (i,j), we merge the sets corresponding to both stones. We can use union-find algorithm to merge the sets efficiently.

After merging all the sets, the number of stones that can be removed will be equal to the total number of stones minus the number of disjoint sets.

Following is the Python code for the solution:

“`

class Solution:

def removeStones(self, stones: List[List[int]]) -> int:

parent = {}

def find(x):

if x != parent[x]:

parent[x] = find(parent[x])

return parent[x]
def union(x,y):

parent.setdefault(x,x)

parent.setdefault(y,y)

parent[find(x)] = find(y)

```
for x,y in stones:
union(x+10001, y)
return len(stones)-len({find(x+10001) for x,y in stones})
```

“`

In this code, we first define parent dictionary to hold the parent for each stone. We define two functions: find(x) which returns the root parent of a set and union(x,y) which merges the sets containing elements x and y.

We iterate through each stone in the input array and merge the sets of stones in the same row and column using union(x,y).

Finally, we return the total number of stones in the input array minus the number of disjoint sets using len(stones)-len({find(x+10001) for x,y in stones}). We add 10001 to each row index to differentiate between row and column indices as they can be equal.

This code has time complexity of O(N\alpha(N)) where N is the number of stones and \alpha is the Inverse-Ackermann function.

## Step by Step Implementation For Most Stones Removed With Same Row Or Column

There are a few different ways to approach this problem. One way would be to keep track of which stones have been removed and which are still remaining. Then, for each stone that is remaining, check to see if there are any other stones in the same row or column. If so, remove those stones as well. Repeat this process until there are no more stones remaining. Another approach would be to keep track of which rows and columns have been visited. Then, for each stone that is remaining, check to see if the row or column has been visited. If not, visit the row or column and remove all of the stones. Repeat this process until there are no more stones remaining.

class Solution: def removeStones(self, stones: List[List[int]]) -> int: # union find # for each stone, connect it with all stones with same row or column # return the number of connected components - 1 # create a parent map to store the parent of each stone parent = {} # for each stone, connect it with all stones with same row or column for i, j in stones: # if the stone is not in the parent map, add it if (i, j) not in parent: parent[(i, j)] = (i, j) # for all other stones with same row as stone (i, j) for k in range(j + 1, len(stones[0])): # if the stone (i, k) is not in the parent map, add it if (i, k) not in parent: parent[(i, k)] = (i, k) # connect stone (i, k) with stone (i, j) self.union((i, j), (i, k), parent) # for all other stones with same column as stone (i, j) for k in range(i + 1, len(stones)): # if the stone (k, j) is not in the parent map, add it if (k, j) not in parent: parent[(k, j)] = (k, j) # connect stone (k, j) with stone (i, j) self.union((i, j), (k, j), parent) # return the number of connected components - 1 return len(set(self.find(stone, parent) for stone in stones)) - 1 # find the root of the given stone def find(self, stone, parent): # if the stone is its own parent, it is the root if parent[stone] == stone: return stone # otherwise, find the root of the parent of the stone return self.find(parent[stone], parent) # connect the given stones def union(self, stone1, stone2, parent): # find the roots of the two stones root1 = self.find(stone1, parent) root2 = self.find(stone2, parent) # connect the two roots parent[root2] = root1

var removeStones = function(stones) { // create a map to store the mapping of each stone's position to its connected stones let map = new Map(); // loop through each stone for (let i = 0; i < stones.length; i++) { let stone = stones[i]; // if the map doesn't have an entry for the stone's row, create one if (!map.has(stone[0])) { map.set(stone[0], new Set()); } // if the map doesn't have an entry for the stone's column, create one if (!map.has(stone[1])) { map.set(stone[1], new Set()); } // add the stone's position to its row and column entries in the map map.get(stone[0]).add(i); map.get(stone[1]).add(i); } // create a visited set to keep track of which stones have been visited let visited = new Set(); // create a variable to store the number of connected components let numComponents = 0; // loop through each stone for (let i = 0; i < stones.length; i++) { // if the stone has not been visited if (!visited.has(i)) { // mark the stone as visited visited.add(i); // increment the number of connected components numComponents++; // create a queue to store the stones in the same connected component as the current stone let queue = [i]; // while the queue is not empty while (queue.length > 0) { // get the next stone in the queue let stone = queue.shift(); // get the row and column of the stone let row = stones[stone][0]; let col = stones[stone][1]; // get the stones connected to the stone's row let rowConnections = map.get(row); // get the stones connected to the stone's column let colConnections = map.get(col); // loop through the stones connected to the stone's row for (let j of rowConnections) { // if the stone has not been visited if (!visited.has(j)) { // mark the stone as visited visited.add(j); // add the stone to the queue queue.push(j); } } // loop through the stones connected to the stone's column for (let j of colConnections) { // if the stone has not been visited if (!visited.has(j)) { // mark the stone as visited visited.add(j); // add the stone to the queue queue.push(j); } } } } } // return the number of stones - the number of connected components (this will be the maximum number of stones that can be removed) return stones.length - numComponents; };

//Solution: int removeStones(vector>& stones) { int n = stones.size(); //Create a graph with the stones as nodes //Connect nodes that are in the same row or column unordered_map > graph; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) { graph[i].insert(j); graph[j].insert(i); } } } //Do a DFS from each node to find connected components //The number of stones in each connected component - 1 is the number of moves needed to remove all stones in that component int res = 0; vector visited(n); for(int i = 0; i < n; i++) { if(!visited[i]) { int componentSize = 0; stack st; st.push(i); visited[i] = true; while(!st.empty()) { int curr = st.top(); st.pop(); componentSize++; for(int next : graph[curr]) { if(!visited[next]) { st.push(next); visited[next] = true; } } } res += componentSize - 1; } } return res; }

using System; using System.Collections.Generic; public class Solution { public int RemoveStones(int[][] stones) { // keep track of visited stones HashSetvisited = new HashSet (); // keep track of number of stones removed int count = 0; // for each stone, check if it has been visited. // if not, remove all stones in the same row or column for(int i = 0; i < stones.Length; i++) { int[] stone = stones[i]; if(!visited.Contains(stone)) { RemoveStone(stone, stones, visited); count++; } } // return number of stones removed return stones.Length - count; } // remove all stones in the same row or column as stone public void RemoveStone(int[] stone, int[][] stones, HashSet visited) { Queue queue = new Queue (); queue.Enqueue(stone); visited.Add(stone); // while queue is not empty while(queue.Count != 0) { int[] s = queue.Dequeue(); // for each stone in the same row or column as s for(int i = 0; i < stones.Length; i++) { int[] curr = stones[i]; // if curr has not been visited and is in the same row or column as s if(!visited.Contains(curr) && (curr[0] == s[0] || curr[1] == s[1])) { // add curr to queue and mark as visited queue.Enqueue(curr); visited.Add(curr); } } } } }