# Most Stones Removed with Same Row or Column LeetCode Solution

Difficulty Level Medium
Bfs Dfs Dsu GraphViews 1454

## Problem Statement

Most Stones Removed with Same Row or Column LeetCode Solution says that On a 2D plane

we place `n` stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.  An array `stones` of length `n` where `stones[i] = [x`i`, y`i`]` represents the location of the `i`th stone. We have to find the largest number of stones to be removed.

Example 1:

Input:

``` stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
```

Output:

``` 5
```

Explanation:

``` One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
```

Example 2:

Input:

``` stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
```

Output:

``` 3
```

Explanation:

``` One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
```

Example 3:

Input:

``` stones = [[0,0]]
```

Output:

``` 0
```

Explanation:

``` [0,0] is the only stone on the plane, so you cannot remove it.
```

Constraints:

• `1 <= stones.length <= 1000`
• `0 <= x`i`, y`i` <= 10`4
• No two stones are at the same coordinate point.

## Approach

### Idea

1. The idea here is that we can remove all stones from the group of connected stones except the last one.
2. If stone `a` and stone `b` are in the same column/row, we connect them as a component. That means we can make them as connected components.
3. The maximum number of stones can be removed = the number of stones-connected components.
4. For finding the connected components we can use DFS/BFS or Union find algorithms.  ## Code

### C++ Solution

```class Solution {
public:
#define ll int
ll par;
void make()
{
ll i;
for(i=0;i<=10000;i++)
par[i]=i;
}
ll find(ll x)
{
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
ll unite(ll x,ll y)
{
ll p1=find(x);
ll p2=find(y);
if(p1!=p2)
{
par[p1]=p2;
}
return 0;
}
int removeStones(vector<vector<int>>& stones) {
make();
set<ll>s;
ll i,j,n=stones.size();
for(i=0;i<n;i++)
{

for(j=i+1;j<n;j++)
{

if(stones[i]==stones[j] or stones[i]==stones[j])
{
unite(i,j);
}
}
}
ll cnt=0;
for(i=0;i<n;i++)
{
if(par[i]==i)cnt++;
}
return stones.size()-cnt;
}
};```

### Java Solution

```class Solution {
int[] par=new int;
void make()
{
int i;
for(i=0;i<=10000;i++)
par[i]=i;
}

int find(int x)
{
if(par[x]==x)
return x;
return par[x]=find(par[x]);
}

int unite(int x,int y)
{
int p1=find(x);
int p2=find(y);
if(p1!=p2)
{
par[p2]=p1;
}
return 0;
}
public int removeStones(int[][] stones) {
int i,j,n=stones.length;
make();

for(i=0;i<n;i++)
{

for(j=i+1;j<n;j++)
{

if(stones[i]==stones[j] || stones[i]==stones[j])
{
unite(i,j);
}
}
}
int cnt=0;
for(i=0;i<n;i++)
{
if(par[i]==i)cnt++;
}
int k=n-cnt;
return k;

}
}

```

## Complexity Analysis of Most Stones Removed with Same Row or Column LeetCode Solution

### Time Complexity

Time complexity is O(N*N). As we are looping in the array to connect them. Where N is the array size.

### Space Complexity

Space complexity is 0(N). We are taking extra space to store the parents.

Translate »