# 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)):
# 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)) {
map.set(stone, new Set());
}
// if the map doesn't have an entry for the stone's column, create one
if (!map.has(stone)) {
map.set(stone, new Set());
}
// add the stone's position to its row and column entries in the map
}
// 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
// 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];
let col = stones[stone];
// 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
// 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
// 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] == stones[j] || stones[i] == stones[j]) {
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
HashSet visited = 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);

// 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 == s || curr == s)) {
// add curr to queue and mark as visited
queue.Enqueue(curr);
}