# 947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a _move _consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

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

Example 2:

``````Input:
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
``````

Example 3:

``````Input:
stones = [[0,0]]
Output: 0
``````

Note:

1. `1 <= stones.length <= 1000`
2. `0 <= stones[i][j] < 10000`

Thoughts:

1. Union Find: Similar to number of islands, where a "connected" graph is a island. Unify the row and col index (Original Post)
1. Optimization: Path Compression, Union by rank (see 305. Number of Islands II)
2. DFS: number of islands -> island: collection of points connected by row or column (Original Post)

Code: T: O(n) -> O(1)

``````class Solution {
public:
unordered_map <int, int> f;
int islands = 0;

int removeStones(vector<vector<int>>& stones) {
for(int i = 0; i < stones.size(); i++){
unify(stones[i][0], ~stones[i][1]);
}
return stones.size() - islands;
}

int find(int x){
if (!f.count(x)) f[x] = x, islands++;
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}

void unify(int x, int y){
x = find(x), y = find(y);
if (x != y) f[x] = y, islands--;
}

};
``````

Code: T:O(n) -> O(1): Path Compression + Union by rank

``````class Solution(object):
def removeStones(self, stones):
"""
:type stones: List[List[int]]
:rtype: int
"""
UF = {}
"""
Union by rank
rank = {}
"""
def find(x):
while UF[x] != x:
"""
Path Compression
UF[x] = UF[UF[x]]
"""
x = UF[x]
return x

def union(x,y):
UF.setdefault(x, x);
UF.setdefault(y, y);

"""
Union by rank
rank.setdefault(x, 0);
rank.setdefault(y, 0);
if rank[x] > rank[y]:
x, y = y, x
rank[y] += rank[x] == rank[y]
"""
UF[find(x)] = find(y)

for i, j in stones:
union(i, ~j);

cc = {find(x) for x in UF} # set
return len(stones) - len(cc)
``````

Code: DFS: discard points for the same island

``````class Solution:
def removeStones(self, stones):
def dfs(i, j):
for y in rows[i]:
if (i, y) in points:
dfs(i, y)
for x in cols[j]:
if (x, j) in points:
dfs(x, j)
points, island, rows, cols = {(i, j) for i, j in stones}, 0, collections.defaultdict(list), collections.defaultdict(list)
for i, j in stones:
rows[i].append(j)
cols[j].append(i)
for i, j in stones:
if (i, j) in points:
dfs(i, j)
island += 1
return len(stones) - island
``````